Главная » SQL, Базы данных » В-деревья и индексация БД

0

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

Основная  причина  применения  любого  индекса  состоит  в  том,  что  он  позволяет   исключить необходимость в физическом последовательном просмотре индексированного  файла.  Но физический последовательный  просмотр  все  еще  требуется  выполнять  в  индексе.  Если  индексированный  файл становится очень большим, то и сам индекс может приобрести  весьма значительные размеры, поэтому последовательный просмотр даже только одного индекса  может потребовать довольно продолжительного времени. Решение этой проблемы является таким же, как и прежде — индекс рассматривается просто как обычный  файл  и  на  нем  формируется  другой  индекс  (индекс  на  индексе).  Эта  идея  может  быть осуществлена на любом  необходимом количестве уровней (на практике  чаще всего применяется три уровня; для того  чтобы файлу потребовалось больше трех уровней индексации,  он действительно должен  стать  очень большим). Каждый уровень индекса действует в качестве неплотного индекса для нижележащего уровня (разумеется, он обязательно должен быть неплотным, так как в противном случае использование еще одного уровня не позволило бы добиться каких-либо преимуществ —  на уровне п находилось бы такое же количество элементов, как и на уровне n+1, и поэтому просмотр индекса более высокого уровня занимал бы такое же время, как и просмотр предыдущего).

Теперь перейдем к описанию В-деревьев. Любое В-дерево представляет собой один из  конкретных типов  древовидного  индекса.  В-деревья  как  таковые  были  впервые  предложены  Байером  (Bayer)  и Маккрейтом  (McCreight)  в  1972  году  [Г.16].  С  того  времени  было  проанализировано множество вариантов одной и той же основной идеи, как самим Байером, так и многими другими исследователями; как уже было сказано, В-деревья того или иного типа в настоящее время, вероятно, составляют наиболее широко  применяемую структуру  хранения во  всех современных системах баз данных. Ниже описан вариант, который рассматривается в работе Кнута (Knuth) [Г. 1]. Кстати, следует отметить, что структура индекса в методе виртуального доступа к памяти (Virtual Storage Access Method — VSAM) компании IBM [Г. 18] весьма напоминает структуру Кнута; тем не менее, версия VSAM была разработана независимо и включает  собственные дополнительные средства, такие как использование методов сжатия. В  действительности, вариант, предшествующий структуре VSAM, был описан еще в 1969 году [Г. 19].

В  варианте  Кнута, описанном  ниже,  индекс  состоит  из  двух  частей  (для  обозначения  которых используется терминология VSAM) — последовательного набора (sequence set) и индексного набора (index set).

■       Последовательный набор представляет собой одноуровневый индекс к фактическим данным; этот индекс обычно является плотным, но может быть и неплотным, если индексированный файл кластеризован по индексированному полю. Элементы этого индекса (безусловно) сгруппи рованы в страницы, а страницы (безусловно) соединены цепочками указателей таким образом, что логическое упорядочение, представленное индексом, можно восстановить, считывая записи в физической последовательности на первой странице в цепочке, затем — записи в физической последовательности на второй странице в цепочке и т.д. Таким образом, последовательный набор обеспечивает быстрый последовательный доступ к индексированным данным.

■       Индексный набор, в свою очередь, дает возможность получить быстрый прямой доступ к после довательному набору (и таким образом также и к самим данным). Индексный набор фактически представляет собой древовидный индекс к последовательному набору; в действительности, строго говоря, настоящим В-деревом является именно индексный набор. Комбинация индекс ного набора и последовательного набора иногда именуется "В*-деревом". Верхний уровень индексного набора состоит из единственного узла (т.е. из одной страницы, но, безусловно, содержащей много элементов индекса, как и все другие узлы). Верхний узел индекса называется корнем.

На рис. Г. 13 приведен простой пример. Этот рисунок можно пояснить следующим образом. Прежде всего, значения 6, 8, 12, …, 97, 99— это значения индексированного поля, скажем,  F.  Рассмотрим верхний узел, который состоит из двух значений F (50 и 82) и трех указателей  (фактически  номеров страниц). Записи данных со значением F, меньшим или равным 50, можно  найти (в конечном итоге), проследовав по левому указателю из этого узла, аналогичным образом, записи со значением F, большим чем 50 и меньшим или равным 82, можно найти, следуя по среднему указателю, а записи со значением F, большим чем 82, можно получить, следуя по  правому  указателю. Другие узлы в этом индексном наборе интерпретируются аналогичным  образом; обратите внимание на то, что (например), перейдя по правому указателю из первого узла на второй узел, можно получить все записи со значением F, большим чем 32, а также меньшим или  равным 50 (в силу того факта, что мы уже перешли по левому указателю из узла более высокого уровня).

Тем не менее, В-дерево (т.е. индексный набор), показанное на рис. Г. 13, не совсем реалистично по описанным ниже причинам.

■       Во-первых, все узлы В-дерева обычно не содержат одинаковое количество значений данных.

■       Во вторых, в этих узлах, как правило, находится определенный объем свободного пространства.

Вообще говоря, любое "В-дерево порядка п" имеет не меньше п и не больше 2п значений данных в любом конкретном узле (и если в узле находится к значений данных, то имеется также к+1 указатель). Ни одно значение данных не встречается в дереве больше одного раза. Ниже приведен алгоритм поиска конкретного значения V в структуре, показанной на рис. Г.13 (см.  стр.  1334); алгоритм для В*-дерева общего вида порядка п представляет собой просто обобщение данного алгоритма.

set N to the root node ;

do until N is a sequence-set node ;

let X, Y (X < Y) be the data values in node N ;

if V < X    then set N to the left  lower node of N ; if X < V < Y then set N to the middle lower node of N ; if V > Y    then set N to the right  lower node of N ;

end ;

if V occurs in node N then exit /* найдено */ ;                                        if V does

not occur in node N then exit /* не найдено */ ;

Выполнение операций вставки и удаления может привести к тому, что дерево станет  несбалансированным, и в этом состоит важная проблема, связанная с использованием любых древовидных структур в целом. Дерево является несбалансированным, если не все листовые  узлы  находятся на одном и том же  уровне, иными словами, если  различные листовые узлы  находятся на  разных  расстояниях от корневого  узла. Поскольку  в процессе поиска  в  дереве  доступ к  диску  требуется для перехода к каждому узлу, в несбалансированном  дереве  такой показатель, как  время поиска, становится почти непредсказуемым.

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

В отличие от этого, замечательным преимуществом В-деревьев является то, что алгоритмы вставки и удаления гарантируют, что дерево всегда остается сбалансированным. (По этой причине  иногда приходится слышать, что аббревиатура "В" в термине "В-дерево" обозначает "balanced" —  сбалансированный.) Ниже кратко рассматривается процедура вставки нового значения, скажем, V, в В-дерево порядка п. В применяемом при этом алгоритме рассматривается только  индексный набор, поскольку  (как  было описано  выше)  собственно  В-деревом  является  именно  индексный  набор;  чтобы  распространить действие этого алгоритма также на последовательный набор, требуется лишь простейшее дополнение.

■       Вначале выполняется алгоритм поиска для обнаружения не узла последовательного набора, а того узла (скажем, N) на самом нижнем уровне индексного набора, к  которому логически относится значение V. Если узел N содержит свободное пространство, то значение V вставляется в N и процесс завершается.

■        В противном случае узел N (который таким образом содержит 2п значений) разделяется на два узла, N1 и N2. Допустим, что S — ряд первоначальных 2п значений наряду с новым значением V в их логической последовательности. Наименьшие п значений из ряда S помещаются в левый узел, N1, наибольшие п значений из ряда S помещаются в правый узел, N2, а среднее значение, скажем, W, продвигается в родительский узел узла N, скажем, Р, для использования в качестве разделительного значения для узлов N1 и N2. В дальнейшем при поиске значения и этот поиск после достижения узла Р будет направлен в узел N1, если U < W, и в узел  N2, если  и > W.

■        Теперь предпринимается попытка вставить значение W в узел  Р и описанный процесс повто ряется.

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

Разумеется,  алгоритм  удаления по существу  является обратным  по отношению  к  только  что описанному алгоритму вставки. Изменение значения осуществляется путем удаления старого значения и вставки нового.

Источник: Дейт К. Дж., Введение в системы баз данных, 8-е издание.: Пер. с англ. — М.: Издательский дом «Вильямс», 2005. — 1328 с.: ил. — Парал. тит. англ.

По теме:

  • Комментарии