Каковы преимущества T-деревьев перед B +/- деревьями?

Question

Я изучил определения T-деревьев и B- / B + деревьев. Из статей в Интернете я понимаю, что B-деревья работают лучше в иерархической памяти, такой как дисководы и кэшированная память.

Что я не могу понять, так это почему T-деревья использовались / используются даже для плоской памяти?

Они рекламируются как эффективная альтернатива деревьям AVL.

В худшем случае все конечные узлы T-дерева содержат только один элемент, а все внутренние узлы содержат минимально допустимое количество, близкое к полному. Это означает, что в среднем используется только половина выделенного пространства. Если я не ошибаюсь, это то же самое использование, что и в худшем случае B-деревьев, когда узлы B-дерева наполовину заполнены.

Предполагая, что оба дерева хранят ключи локально в узлах, но используют указатели для ссылки на записи, единственное отличие состоит в том, что B-деревья должны хранить указатели для каждой из ветвей. Как правило, это может привести к накладным расходам до 50% или меньше (по T-деревьям), в зависимости от размера ключей. Фактически это близко к издержкам, ожидаемым в деревьях AVL, при условии отсутствия родительского указателя, записей, встроенных в узлы, ключей, встроенных в записи. Это ожидаемое повышение эффективности, которое мешает нам использовать B-деревья вместо этого?

T-деревья обычно реализуются поверх деревьев AVL. Деревья AVL более сбалансированы, чем B-деревья. Может ли это быть связано с применением T-деревьев?

Answer 1

Я могу дать вам личную историю, которая охватывает половину ответа, поэтому я написал некоторый код на Паскале для программирования B + деревья около 18 лет назад.

моей целевой системыЭто был ПК с двумя дисководами, мне нужно было хранить индекс в энергонезависимой памяти, и я хотел лучше понять, что я изучал в университете.Я был очень недоволен производительностью коммерческого пакета, возможно, DBase III, или какого-то продукта Fox, я не могу вспомнить.

В любом случае: мне нужны были следующие операции:

• lookup
• вставка
• удаление
• следующий элемент

• предыдущий элемент

• максимальный размер индекса былнеизвестно

• , поэтому данные должны были находиться на диске
• , каждый доступ к поддержке стоил очень дорого
• чтение всего блока стоило столько же, сколько считывание одного байта

B + -дерево сделали так, чтобы маленький медленный ПК действительно пролистывал данные!

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

Answer 2

На самом деле разница заключается в системе, которую вы используете. Как прокомментировал мой преподаватель в университете: если ваша проблема заключается в нехватке памяти, или в нехватке жесткого диска, определите, какое дерево и в какой реализации вы будете использовать. Скорее всего, это будет дерево B +.

Поскольку существуют сотни реализаций, например, с 2-направленной очередью и однонаправленными очередями, в которых вам нужно зацикливать мысленные элементы, а также существует несколько способов хранения индекса и его извлечения, что определит реальные минусы и минусы любой реализации. .