Основы проектирования реляционных баз данных



Индекс со структурой B-Tree


Индекс на основе сбалансированной иерархической структуры, или индекс B-Tree (Balanced Tree structured object), используется как индекс по умолчанию в СУБД Oracle. Эта структура напоминает дерево (если смотреть снизу вверх), в котором сначала считывается самый верхний блок - корневой узел (root), затем блок на следующем уровне - блок-ветвь (branch) и так до тех пор, пока не будет извлечен блок-лист (leaf) с идентификатором строки. Значения ключа сохраняются в индексе (рис. 11.1). Такая структура позволяет сократить до минимума число операций ввода/вывода. Для получения идентификатора строки обычно требуется одно посещение блок-листа, т.е. физической страницы базы данных, отведенной под индекс.

Концептуальная организация B-Tree индекса

Рис. 11.1.  Концептуальная организация B-Tree индекса

Замечание. Следует отметить два случая, когда после выборки идентификатора строки из индекса может понадобиться несколько посещений физической страницы индекса: 1) когда строка имеет длину более одной физической страницы, так называемая расщепленная строка; 2) когда строка за время своего существования в базе данных увеличилась и была перемещена из исходной страницы в другую, так называемая мигрировавшая строка.

Индекс B-Tree характеризуется количеством уровней в индексе (height). Чем меньше уровней, тем выше производительность.

Индекс B-Tree - это физический объект реляционной базы данных, организованный по принципу сбалансированной иерархической структуры и обладающий набором свойств. Сформулируем некоторые свойства индексов со структурой B-Tree.

  • Количество операций ввода/вывода, необходимых для получения идентификатора строки, зависит от числа уровней ветвления дерева. По мере увеличения индекса в результате добавление новых данных, СУБД добавляет в него новые уровни, чтобы обеспечить сбалансированность дерева. Однако в действительности таких уровней редко бывает более четырех.
  • Корневой узел и узлы - ветви индекса сжимаются и поэтому содержат ровно столько начальных байтов значения ключа, сколько нужно для того, чтобы отличить его от других значений.


    Содержание  Назад  Вперед