DeepEdit!

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

Структура данных, используемая Oracle для хранения индекса, называется 

Ъ*-деревом. 

Такое построение верно даже для двоичных индексов, хотя в этом случае содержимое листьев отличается от содержимого регулярного индекса.

Верхний узел индекса называется корневым узлом, узлы второго уровня -
ветвями, а узлы нижнего уровня - листьями. Верхние блоки (ветви) индекса со-
держат данные индекса, указывающие на блоки индекса более низкого уровня.
Блоки индекса самого нижнего уровня (листья) содержат индексные данные
для каждого значения и соответствующие им        применяемые для размещения фактической строки. Связи листьев между собой устанавливаются через

двунаправленный список, позволяющий осуществлять обоюдные перемещения

листьев. Индексы в столбцах, содержащих символьные данные, основываются на двоичных значениях символов из набора символов базы данных.

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

за тем исключением, что у        может быть до   двоичных узлов в отличие

от двоичного дерева, у которого только две дочерние вершины.