Галерея
7757 8119 8300 8698 8817 9504 9722 9937
Интересные записи
Новое на сайте
Топовые новости

Индексы баз данных реализованы в виде B-дерева

Индексы баз данных реализованы в виде B-дереваБольшинство индексов баз данных реализованы в виде B-дерева — в них применяется алгоритм B-дерева, минимизирующий число обращений к жесткому диску, которое требуется для нахождения нужной записи. Так как жесткий диск имеет механические компоненты, операции чтения и записи на него занимают намного больше времени, чем на чисто электронные устройства. По сравнению с обращением к оперативной памяти доступ к элементу данных на жестком диске занимает в тысячи раз больше времени. B-дерево содержит узлы со множеством ветвей, связывающих их с дочерними узлами. Простейшая версия B-дерева носит название Двоичного дерева — в нем каждый узел имеет всего два дочерних. На рис. 4.5 продемонстрирован процесс поиска числа 100 в двоичном дереве. Этот алгоритм крайне прост. Поиск начинается с вершины; если значение верхнего узла больше искомого, мы перемещаемся влево, в противном случае — вправо. И так продолжается до тех пор, пока не будет найдено искомое значение или пока не будет достигнут листовой (крайний) узел. Индексы могут создаваться как уникальные и как неуникальные. Уникальные индексы неявно создаются для столбцов, имеющих ограничения UNIQUE или PRIMARY KEY. В них не допускается повторения значений. Неуникальные индексы создаются по столбцу или группе столбцов без каких-либо ограничений на дублирование значений. Индексы могут создаваться как по одному столбцу, так и по их комбинации. Последний подход может оказаться полезным в случаях, когда в условии WHERE часто встречается данная комбинация столбцов. К примеру, если в базе данных часто выполняется поиск заказов, осуществленных конкретным клиентом в заданный день, можно создать неуникальный индекс по комбинации столбцов ORDHDR CUSTID FN и ORDHDR CREATEDATE D таблицы ORDER HEADER. В SQL:2003 не содержится каких-либо стандартов для индексов (наличие индексов вообще не требуется), однако практически все производители СУБД предлагают свои механизмы создания индексов, поскольку без них любая производственная база данных работала бы очень медленно.