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