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

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

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

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

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

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

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

12
задан Dukeling 16 November 2013 в 22:31
поделиться