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