В- деревья
В традиционной реляционной СУБД в индексной странице В-дерева как значение индекса, так и указатель на данные хранятся в самой записи В-дерева. Узел В-дерева (дисковая страница) состоит из нескольких записей В-дерева, каждая из которых содержит значение индекса, а также номер страницы следующего соответствующего узла дерева или номер страницы с искомой строкой данных. Как показано на рисунке, получаемое в результате дерево имеет очень маленькую глубину - оно невысокое и широкое. Такая структура идеальна для уменьшения числа дисковых операций ввода/вывода. Структура В-деревьев как раз на это и рассчитана - сократить число операций обмена с диском, необходимых для извлечения требуемых данных. В-деревья позволяют решить эту задачу: во-первых, значения индексов хранятся в самих узлах В-дерева, а во-вторых, в узле содержится максимально возможное число индексированных записей. Эта структура, идеальная в случае, когда данные и индексы хранятся на диске, гораздо хуже срабатывает, когда данные располагаются в оперативной памяти. Если данные и так находятся в оперативной памяти, цель схемы индексирования - сократить число требуемых для поиска циклов процессора, а не дисковых операций ввода/вывода. Вычислительная мощность процессора растрачивается на сравнение значений индекса в В-дереве, а также на управление буферами, которые содержат данные и индексы, уже загруженные с диска в память. На Рис. 1 приведена структура индекса на основе В-дерева. Каждая вершина индекса на основе Т-дерева содержит несколько указателей на записи таблицы базы данных на диске. В Oracle TimesTen, в отличие от традиционных систем управления базами данных, используются индексы на основе Т-деревьев. Т-дерево оптимизировано для доступа к оперативной памяти и имеет гораздо более экономичную структуру, чем В-дерево. В отличие от В-деревьев, в каждом узле Т-дерева хранится 64 значения ключа индекса, каждое из которых имеет прямую ссылку на адрес в памяти, где хранится индексируемая запись базы данных. Для навигации по дереву используются указатели "меныше-или-равно" и "больше", представляющие собой непосредственные ссылки на адрес в памяти, а не на дисковую страницу. Всего за две операции сравнения алгоритм поиска Т-дерева "узнает": находится ли искомое значение в текущем узле или где-либо еще в памяти. И с каждым переходом по указателю узла индекса область поиска сокращается вдвое.
Использование индексов на основе Т-дерева помогает решить задачу управления данными в TimesTen - уменьшить требования к памяти, отказаться от дисковых операций ввода/вывода и упростить программу поиска.
|
