В- деревья

В традиционной реляционной СУБД в индексной странице В-дерева как значение индекса, так и указатель на данные хранятся в самой записи В-дерева. Узел В-де­рева (дисковая страница) состоит из нескольких записей В-дерева, каждая из ко­торых содержит значение индекса, а также номер страницы следующего соответ­ствующего узла дерева или номер страницы с искомой строкой данных. Как пока­зано на рисунке, получаемое в результате дерево имеет очень маленькую глубину - оно невысокое и широкое. Такая структура идеальна для уменьшения числа ди­сковых операций ввода/вывода. Структура В-деревьев как раз на это и рассчита­на - сократить число операций обмена с диском, необходимых для извлечения тре­буемых данных. В-деревья позволяют решить эту задачу: во-первых, значения ин­дексов хранятся в самих узлах В-дерева, а во-вторых, в узле содержится макси­мально возможное число индексированных записей.

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

На Рис. 1 приведена структура индекса на основе В-дерева. Каждая вершина ин­декса на основе Т-дерева содержит несколько указателей на записи таблицы ба­зы данных на диске.

В Oracle TimesTen, в отличие от традиционных систем управления базами данных, используются индексы на основе Т-деревьев. Т-дерево оптимизировано для до­ступа к оперативной памяти и имеет гораздо более экономичную структуру, чем В-дерево. В отличие от В-деревьев, в каждом узле Т-дерева хранится 64 значения ключа индекса, каждое из которых имеет прямую ссылку на адрес в памяти, где хранится индексируемая запись базы данных. Для навигации по дереву использу­ются указатели "меныше-или-равно" и "больше", представляющие собой непо­средственные ссылки на адрес в памяти, а не на дисковую страницу. Всего за две

операции сравнения алгоритм поиска Т-дерева "узнает": находится ли искомое значение в текущем узле или где-либо еще в памяти. И с каждым переходом по указателю узла индекса область поиска сокращается вдвое.

Использование индексов на основе Т-дерева помогает решить задачу управления данными в TimesTen - уменьшить требования к памяти, отказаться от дисковых операций ввода/вывода и упростить программу поиска.