[МУЗЫКА]
[МУЗЫКА] Рассмотрим
наиболее популярный метод для построения индексов — B-дерево.
Индекс на основе B-дерева имеет внутренние, или индексные,
и листовые вершины.
Листовые вершины находятся на самом нижнем уровне дерева и
содержат непосредственно записи, которые мы храним в таблице.
Что же включается в индексные вершины?
Как они строятся?
В индексные вершины мы включаем пары — это минимальное значение ключа в блоке,
на который ссылается индексный блок, и адрес блока.
Дадим сначала свойства B-дерева, а затем рассмотрим конкретный пример,
чтобы структура B-дерева была понятной.
B-дерево — это сбалансированная структура.
В чем заключается сбалансированность?
В том, что у нас спуск от корня дерева до любой листовой вершины происходит за
одинаковое количество шагов.
Листовые вершины могут быть связаны списком — либо направленным в одну строну,
либо двунаправленными списками.
Рассмотрим пример.
Давайте построим B-дерево на основе нашей таблице студентов.
Мы выбрали в качестве первичного ключа номер зачетки или идентификатор студента.
Мы должны сначала первым делом упорядочить наши записи во
всей таблице согласно возрастанию этого поля.
Вот на этом слайде вы видите сначала неупорядоченную таблицу.
На следующем слайде мы упорядочили таблицу и разместили строки таблицы в блоках.
Вся наша таблица сейчас вместилась в два блока,
в каждом блоке оказалось по три записи.
На следующем уровне построения индекса мы из каждого блока находим минимальные
значения ключа и запоминаем адрес блока, где хранятся эти записи.
Из этих записей, которые содержат пары, — значение ключа и адрес блока,
— мы составляем индексный блок.
Вот на этом примере мы видим, что у нас в индексный блок включены уже
минимальные значения ключа с номерами зачеток наших студентов,
и наши стрелочки указывают, символизируя адрес блока,
где находятся сами записи, содержащиеся в листовых вершинах.
Давайте оценим количество записей, которые разместились в индексных,
или внутренних, вершинах B-дерева.
Из каждого блока мы взяли всего лишь по одной записи,
которые соответствуют минимальному значению ключа.
Кроме того, записи стали короче, потому что сама запись может содержать множество
полей, а мы взяли всего лишь одно поле — значение ключа.
Но тем не менее, если наша таблица очень большая и строк в ней очень много,
то таких индексных блоков может все равно оказаться много.
Тогда мы поступаем следующим образом.
Мы наращиваем еще один индексный уровень.
Мы рассматриваем внутренние вершины нашего индекса,
они также упорядочены у нас по возрастанию значения ключевого поля.
Мы снова находим минимальные значения ключа для каждого блока,
запоминаем адрес блока, где хранятся наши записи,
и помещаем эти данные в следующий уровень нашего B-дерева.
Таким образом мы продолжаем,
пока на верхнем уровне B-дерева не окажется всего лишь один блок.
Как производится поиск при помощи B-дерева?
Поиск всегда начинается с корня.
Мы находим покрывающее значение ключа для нашего искомого,
определяем адрес блока, спускаемся вниз к следующему уровню и так продолжаем,
пока мы не дойдем до листовых блоков.
А на листовом блоке мы считываем непосредственно данные, которые мы ищем.
Давайте рассмотрим на примере.
В нашем построенном B-дереве по номерам зачеток мы будем искать студента,
чей номер зачетки указан на экране.
Покрывающее значение для этого искомого поля обведено кружком.
Мы находим адрес блока следующего уровня,
спускаемся туда и так поступаем каждый раз, пока не доходим до листового
блока и находим там студента с нужным нам номером зачетки.
Как происходит вставка в B-дерево?
Если нам нужно добавить какой-то элемент в B-дерево,
то сначала мы должны определить блок, в который мы должны произвести вставку.
Вначале мы производим поиск по заданному значению ключа вставляемой записи.
Определив нужный блок, мы пытаемся добавить запись туда,
если в блоке есть свободное место.
Если в блоке свободного места нет, то мы разделяем наш блок на два,
и нам придется добавить указатель на этот новый блок в нашу индексную структуру.
Поднимаемся на уровень выше,
смотрим: если ли в нашем индексном блоке есть место для новой пары,
мы добавляем ее туда, если нет, то индексные блоки так же делятся на два.
В худшем случае при добавлении записи у нас может появиться новый уровень
нашего индексного B-дерева.
Далее мы рассмотрим, как применяются индексы на основе B-дерева
и в каких случаях они строятся.
Михайлова Еленадоцент, ИО заведующего кафедрой информационно-аналитических систем СПбГУ
