Индексы на основе B* - дерева

dbstalker, 19 мая

Это самые широко используемые индексы. Цель создания индекса – минимизировать время поиска данных сервером оракла. Реализованы они на основе двоичного дерева поиска. Что-то типа такого (из Тома Кайта):

Блоки самого нижнего уровня называются листовыми вершинами или листовыми блоками(leaf blocks). Именно в них содержаться конкретные идентификаторы строк или их диапазон.

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

Главное для запоминания:

Блоки-ветви содержат значения индекса и адрес других блоков-ветвей или блоков -листьев.

Блоки листья содержат значения индекса и ROWID записи таблицы.

Далее. Листовые блоки образуют двусвязный список. Для чего нужен такой список? Например, для облегчения поиска по конструкции: betweeen значение1 and значение2. Оракл проходит один раз по структуре индекса с самого начала и до листового блока, где находится значение1. А затем просто идет переход по листовым блокам – по двухсвязному списку листовых блоков, до тех пор пока не дойдет до значение2 (это доступ - Index Range Scan ). То есть больше по веткам (branch) ходить не нужно.

Может ли быть неуникальным индекс на основе B* - дерева?

Оракл говорит, что не может. И вот, что для этого делает: к неуникальному индексу просто добавляется идентификатор записи. В результате индекс сортируется по значению ключа индекса, а затем по идентификатору записи.

Концептуально

CREATE INDEX I ON T(X,Y)

означает

CREATE UNIQUE INDEX I ON T(X,Y, ROWID)

Кстати, в уникальном индексе сортировка идет только по значению ключа индекса.

Теперь сделаем дамп всей структуры индекса :

select object_id  id_my_index from dba_objects where owner = 'MY_SCHEMA' and
  object_type = 'INDEX' and
  object_name = 'MY_INDEX_PK';

alter session set events 'immediate trace name treedump level id_my_index';


----- begin tree dump
branch: 0x317431b 51856155 (0: nrow: 2, level: 3)
   branch: 0x3112c2e 51457070 (-1: nrow: 185, level: 2)
      branch: 0x31744ec 51856620 (-1: nrow: 463, level: 1)
         leaf: 0x317431c 51856156 (-1: nrow: 299 rrow: 299)
         leaf: 0x317431d 51856157 (0: nrow: 299 rrow: 299)
         leaf: 0x317431e 51856158 (1: nrow: 299 rrow: 299)
         leaf: 0x317431f 51856159 (2: nrow: 299 rrow: 299)
         leaf: 0x3174320 51856160 (3: nrow: 299 rrow: 299)
         leaf: 0x3174321 51856161 (4: nrow: 299 rrow: 299)
         leaf: 0x3174322 51856162 (5: nrow: 299 rrow: 299)
         leaf: 0x3174323 51856163 (6: nrow: 299 rrow: 299)
         leaf: 0x3174324 51856164 (7: nrow: 299 rrow: 299)
         leaf: 0x3174325 51856165 (8: nrow: 299 rrow: 299)
         leaf: 0x3174326 51856166 (9: nrow: 299 rrow: 299)
         leaf: 0x3174327 51856167 (10: nrow: 299 rrow: 299)
…

По дампу видно, что в нашем индексе есть три уровня ветвей (один корень и две ветки) – строчки начинаются с branch и обширный уровень листовых блоков –строчки начинаются с leaf. nrow ( в нашем случае - 299)- это суммарное количество ключей или строк включая строки, которые отмечены как удаленные, а rrow - количество ключей или строк.

Вторая колонка цифр это адрес блока ( например, 51856156). Этот адрес можно найти и другим образом. Знание адреса блока дает нам возможность найти id файла данных и блока. Что в свою очередь позволит сделать дамп конкретного блока индекса и посмотреть на его содержимое: значение ключей. Дамп делаем вот такой командой:/p>

alter system dump datafile nn block nnnnnn;

Теперь еще о некоторых понятиях.

Высота (HEIGHT) индекса - уровень листовых блоков. В нашем случае это 4. На четвертом уровне находятся листья. Высоту индекса можно определить не только через дамп. Выполним следующие действия:

ANALYZE INDEX 'MY_INDEX_PK'validate structure;

select	from 	index_stats;

Есть еще такое понятие как глубина индекса(Blevel) – количество уровней ветвей, то есть то, что и HEIGHT, но без уровня листовых блоков: BLEVEL = HEIGHT – 1. Эту величину можно определить следующим образом:

select INDEX_NAME, blevel from ALL_INDEXES where INDEX_NAME='MY_INDEX_PK'

Почитайте на досуге еще немного об индексах

Немного полезностей об индексах и их реорганизации К вопросу о реорганизации индексов. Несколько простых советов К вопросу о реорганизации индексов Индексы на основе B* - дерева Как найти листовой индексный блок для конкретной записи таблицы? sys_op_lbid

Тэги: индексы

ОднаКнопка

2 комментария

Прокоментировать

wudu
30 мая 2010 г. в 05:51

"это доступ - Index Skip Scan" надо исправить на "это доступ - Index Range Scan"

dbstalker
31 мая 2010 г. в 09:23

Спасибо за внимание. исправлено.

 

Новый комментарий

Я не спамер: введите суму 0+2



 

От авторов блога

О Блоге - прочитай перед началом.

Задать вопрос и получить ответ - уже решено 94 вопросов

Глоссарий - список терминов и сокращений


 
 

Бизнес форум

Последние темы:

Товары для взрослых
24 мая, 1 ответа
Выделенный сервер
23 мая, 3 ответа
Где скачать 1с
21 мая, 1 ответа