LINUX.ORG.RU

Деление блоков B+Tree.

 


1

2

Если инсертить в дерево возрастающие ключи, что часто и бывает, то самый правый листовой блок будет всё время линейно расти. Потом он поделится, например пополам, пробросив разделитель наверх, и правая половинка снова начнет линейно расти вправо.

А «левые», наполовину заполненные блоки, так и будут лежать, вечно храня половину пустого пространства.

Вот что почитать на тему разных алгоритмов деления? Например в случае выше можно было для листового блока завести две статистики - «число вставок в левую половину» и "-//- в правую". Делить блок обратно пропорционально - т.е. в случае выше «левые» продукты деления бы получались жирные, а правый пустой (и средняя заполненность блока в дереве была бы под 99%, а не 50%), а деления случались бы реже в 2 раза.

Короче интересны такие статистическо-эвристические штуки и мировой опыт. Сырцы постгреса почитываю бывает, до сабжеыой части не дошел.

Ответ на: комментарий от timdorohin

Тем что левые будут хранить треть пустого пространства, а не половину?

А задача требовала 100% на потоковом инсёрте, юзание неких статистик и других подходов.

hlamotron ()
Последнее исправление: hlamotron (всего исправлений: 1)
Ответ на: комментарий от hlamotron

я не знаю за что ты так ненавидишь кнута, но позволю себе процитировать его:

Эксперименты Э. Мак-Крейта (E. McCreight) показали, что такая политика работы вполне успешна. Например, им было найдено, что при 10 буферах и m=121 процесс вставки 10000 ключей в порядке возрастания требует только 22 действительных чтений и только 857 реальных команд записи. Таким образом, большая часть действий выполнялась во внутренней памяти. Далее, полученное дерево содержало всего 835 узлов, лишь на один узел больше, чем минимально возможное значение [10000/(m-1)] = 834; следовательно, память была использована практически на 100%. В этом эксперименте использовалась технология переливания...

anonymous ()
Ответ на: комментарий от i-rinat

когда вы говорите, такое впечатление, что вы бредите... :)

anonymous ()
Ответ на: комментарий от anonymous

Эксперименты Э. Мак-Крейта (E. McCreight) показали,

Спасибо, я лошары кусок.

hlamotron ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.