Сбалансированное дерево
Дерево – это структура данных, используемая во многих СУБД для хранения данных или индексов. Дерево состоит из иерархии узлов (node), в которой каждый узел, за исключением корня (root), имеет родительский (parent) узел, а также один, несколько или ни одного дочернего (child) узла. Корень не имеет родительского узла. Узел, который не имеет дочерних узлов, называется листом (leaf).
Глубина дерева – это максимальное количество уровней между корнем и листом. Глубина дерева может быть различной для разных путей доступа к листам.
Сбалансированное дерево (Balanced-wood), В-дерево, B-Tree – это дерево, у которого глубина дерева одинакова для всех листов.
Степень (degree), порядок (order) дерева – это максимально допустимое количество дочерних узлов для каждого родительского узла. Большие степени обычно используются для создания более широких и менее глубоких деревьев.
Поскольку время доступа в древовидной структуре зависит от глубины, а не от ширины, обычно принято использовать более «разветвленные» и менее глубокие деревья.
Бинарное дерево (binarytree)– это дерево порядка 2, в котором каждый узел имеет не больше двух дочерних узлов.
Усовершенствованные сбалансированные древовидные индексы определяются по следующим правилам:
· Если корень не является лист-узлом, то он должен иметь, по крайней мере, два дочерних узла.
· В дереве порядка n каждый узел (за исключением корня и листов) должен иметь от n /2 до n указателей и дочерних узлов. Если число n /2 не является целым, то оно округляется до ближайшего большего целого.
· В дереве порядка n количество значений ключа в листе должно находиться в пределах от (n – 1)/2 до (n – 1). Если число (n – 1)/2 не является целым, то оно округляется до ближайшего большего целого.
|
|
· Количество значений ключа в нелистовом узле на единицу меньше количества указателей.
· Дерево всегда должно быть сбалансированным, т.е. все пути от корня к каждому листу должны иметь одинаковую глубину.
· Листы дерева связаны в порядке возрастания значений ключа.
Производительность
Для оптимальной производительности запросов индексы обычно создаются на тех столбцах таблицы, которые часто используются в запросах. Для одной таблицы может быть создано несколько индексов. Однако увеличение числа индексов замедляет операции добавления, обновления, удаления строк таблицы, поскольку при этом приходится обновлять сами индексы. Кроме того, индексы занимают дополнительный объем памяти, поэтому перед созданием индекса следует убедиться, что планируемый выигрыш в производительности запросов превысит дополнительную затрату ресурсов компьютера на сопровождение индекса.
Ограничения
Индексы полезны для многих приложений, однако на их использование накладываются ограничения. Возьмёмтакойзапрос SQL:
SELECT first_name FROM people WHERE last_name = 'Франкенштейн';
Для выполнения такого запроса без индекса СУБД должна проверить поле last_name в каждой строке таблицы (этот механизм известен как «полный перебор» или «полное сканирование таблицы», в плане может отображаться словом NATURAL). При использовании индекса СУБД просто проходит по B-дереву, пока не найдёт запись «Франкенштейн». Такой проход требует гораздо меньше ресурсов, чем полный перебор таблицы.
Теперьвозьмёмтакойзапрос:
|
|
SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com';
Этот запрос должен найти всех клиентов, у которых е-мейл заканчивается на @yahoo.com, однако даже если по столбцу email_address есть индекс, СУБД всё равно будет использовать полный перебор таблицы. Это связано с тем, что индексы строятся в предположении, что слова/символы идут слева направо. Использование символа подстановки в начале условия поиска исключает для СУБД возможность использования поиска по B-дереву. Эта проблема может быть решена созданием дополнительного индекса по выражению reverse(email_address) и формированием запроса вида:
SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@yahoo.com');
В данном случае символ подстановки окажется в самой правой позиции (moc.oohay@%), что не исключает использование индекса по reverse(email_address).
Разреженный индекс
Разреженный индекс (sparseindex) в базах данных – это файл с последовательностью пар ключей и указателей. Каждый ключ в разреженном индексе, в отличие от плотного индекса, ассоциируется с определённым указателем на блок в отсортированном файле данных. Идея использования индексов пришла от того, что современные базы данных слишком массивны и не помещаются в основную память. Данные обычно делятся на блоки и размещаются в памяти поблочно. Однако поиск записи в БД может занять много времени. С другой стороны, файл индексов или блок индексов намного меньше блока данных и может поместиться в буфере основной памяти, что увеличивает скорость поиска записи. Поскольку ключи отсортированы, можно воспользоваться бинарным поиском. В кластерных индексах с дублированными ключами разреженный индекс указывает на наименьший ключ в каждом блоке.