Блог

Есть ли особая причина, по которой B -дерево предпочтительнее при реализации более масштабной системы баз данных, чем куча Фибоначчи? Из анализа сложности на изображении может показаться, что куча Фибоначчи быстрее.

Дерево B — это дерево поиска, а не куча. Изображение сравнивает не кучу Фибоначчи с B -деревом, а с двоичной кучей.

Сравнение кучи и дерева поиска

Куча — это структура данных, которая обеспечивает отложенный порядок, т. Е. Чтобы получить i^-е значение в отсортированном порядке, вам придется изменять кучу по мере извлечения из нее значений. Это верно для обеих реализаций кучи в изображении, которым вы поделились.

Дерево поиска больше ориентировано на порядок. Вы можете перебирать его значения по порядку за O (n) раз, не внося никаких изменений в дерево. Для кучи, которая будет равна O (nlogn), поскольку вам потребуется n extract-min операций, и куча теряет значения, которые вы извлекаете из нее.

Вы написали:

Есть ли особая причина, по которой B -дерево предпочтительнее при реализации более масштабной системы баз данных

Куча не является полезной структурой данных для индексации данных в системах баз данных, поскольку порядок не известен без изменений, а узлы при чтении в упорядоченной последовательности разбросаны по разным местам на диске.

Дерево поиска лучше подходит для этой цели. Среди деревьев поиска те, которые хорошо сочетаются с большими размерами блоков, являются интересным выбором для баз данных, данные которых хранятся на относительно медленных дисках. Таким примером является B-дерево. B -деревья имеют преимущество перед B-деревьями в том, что они хранят значения по порядку внутри связанных конечных блоков, так что они оптимизируются при упорядоченной итерации, в то время как B-деревья занимают немного меньше места, чем B -деревья.

Сравнение двоичной кучи и кучи Фибоначчи

Разница во временной сложности между двоичной кучей и кучей Фибоначчи может быть фактором, влияющим на кучу Фибоначчи. Но поскольку куча Фибоначчи имеет большие накладные расходы, выигрыш будет появляться только для больших наборов данных. В Википедии говорится:

Хотя кучи Фибоначчи выглядят очень эффективными, у них есть следующие два недостатка (как упоминалось в статье «Куча сопряжения: новая форма самонастраивающейся кучи»):

«Они сложны, когда дело доходит до их кодирования. Также они не так эффективны на практике по сравнению с теоретически менее эффективными формами куч, поскольку в их простейшей версии они требуют хранения и обработки четырех указателей на узел по сравнению с двумя или тремя указателями на узел, необходимыми для других структур «.

Эти другие структуры называются двоичной кучей, биномиальной кучей, кучей сопряжения, кучей Бродала и кучей спаривания ранга.

Хотя общее время выполнения последовательности операций, начинающихся с пустой структуры, ограничено приведенными выше границами, выполнение некоторых (очень немногих) операций в последовательности может занять очень много времени (в частности, delete и delete minimum в худшем случае имеют линейное время выполнения). По этой причине кучи Фибоначчи и другие амортизированные структуры данных могут не подходить для систем реального времени.