T-Tree или B-Tree

Question

Алгоритм T-дерева описан в this paper И T * -Tree является улучшением от T-дерева для лучшего использования операций запроса, включая запросы диапазона и содержит все другие хорошие функции T -tree.
Этот алгоритм описан в этой статье «T * -tree: Структура индекса базы данных основной памяти для приложений реального времени».
Согласно этому исследованию, T-Tree быстрее, чем дерево B-tree/B +, когда в память вставляются данные. Я реализовал T-Tree/T * Tree, как они описаны в этих документах, и сравнил производительность с деревом B-tree/B +, но дерево B-tree/B + работает лучше, чем T-Tree/T * Tree во всех тестах случаях (вставка, удаление, поиск).
Я прочитал, что T-Tree является эффективной структурой индекса для базы данных в памяти и используется Oracle TimesTen. Но мои результаты не показали этого.
Если кто-нибудь может знать причину или иметь какие-либо комментарии по этому поводу, будет здорово услышать от нее (или его).

Answer 1

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

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

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

Аналогичные проблемы существуют с перебалансировкой. В мире B-деревьев было разработано и усовершенствовано множество вариантов - начиная с B + и Blink - для достижения желаемых амортизированных характеристик производительности, включая такие аспекты, как параллелизм (блокировка/фиксация) или их отсутствие. Поэтому большую часть времени вы можете просто выйти и найти вариацию B-дерева, которая соответствует вашему профилю производительности, или использовать простое классическое дерево B + и быть уверенными в достойных результатах.

T-деревья более сложны, чем сопоставимые B-деревья, и кажется, что им нечего предложить на дороге производительности вообще, учитывая, что время товарного оборудования с иерархией одноуровневой памяти ' были утеряны на протяжении десятилетий. Мало того, что на жестком диске находится новая память, обратное также верно, а основной памятью является новый жесткий диск. То есть даже без NUMA стоимость доставки данных из основной памяти в иерархию кэша настолько велика, что платит, чтобы минимизировать перенос страниц - это именно то, что делают B-деревья и их варианты, а T-tree - нет. Ближе к процессорному ядру имеет значение количество обращений к кеш-линии/передача, но изображение остается неизменным.

Фактически, если вы берете идею бинарного поиска, что является, по-видимому, оптимальным, и подумайте о способах размещения ключей поиска таким образом, чтобы они хорошо играли с иерархиями памяти (кешами), то вы неизменно оказываетесь в чем-то, что выглядит странно, как B-дерево ...

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