Индексы базы данных B-деревья и списки

Question

Может кто-нибудь объяснить, почему базы данных склонны использовать индексы b-дерева, а не связанный список упорядоченных элементов.

Я думаю так: в дереве B + (используемом большинством баз данных) нествольные узлы представляют собой набор указателей на другие узлы. Каждая коллекция (узел) представляет собой упорядоченный список. Конечные узлы, где находятся все указатели данных, представляют собой связанный список кластеров указателей данных.

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

Просто чтобы было ясно, что наиболее эффективный алгоритм поиска упорядоченного списка со случайным доступом - это двоичный поиск, который имеет производительность O (log n), которая совпадает с b-деревом. Преимущество использования связанного списка, а не дерева, состоит в том, что они не должны быть сбалансированы.

Возможна ли эта структура.

Answer 1

После некоторых исследований и чтения статей я нашел ответ.

Чтобы справиться с большими объемами данных, такими как миллионы записей, индексы должны быть организованы в кластеры.Кластер - это непрерывная группа секторов на диске, которую можно быстро прочитать в память.Обычно они имеют длину около 4096 байт.

Каждый из этих кластеров может содержать набор индексов, которые могут указывать на другие кластеры или данные на диске.Таким образом, если бы у нас был индекс связанного списка, каждый элемент индекса был бы составлен из коллекции индексов, содержащихся в одном кластере (скажем, 100).

Итак, когда мы ищем конкретную запись, как мы узнаем, в каком кластере она находится.Мы выполняем бинарный поиск, чтобы найти рассматриваемый кластер [O (log n)].

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

Что произойдет, если нам нужно более 100 кластеров.У нас должно быть два индекса метаданных, каждый из которых указывает на 100 кластеров (10 000 записей).Ну, этого не достаточно.Давайте добавим еще один кластер метаданных, и теперь мы можем получить доступ к 1 000 000 записей.Итак, как мы узнаем, какой из трех кластеров метаданных нам нужно запросить, чтобы найти целевой кластер данных.Мы могли бы искать то одно, то другое, но это не масштабируется.Поэтому я добавляю еще один кластер мета-метаданных, чтобы указать, какой из трех кластеров метаданных мне нужно запросить, чтобы найти целевой кластер данных.Теперь у меня есть дерево!

Так вот почему базы данных используют деревья.Это не скорость, это размер индексов и необходимость иметь индексы, ссылающиеся на другие индексы.Выше я описал дерево B + - дочерние узлы содержат ссылки на другие дочерние узлы или конечные узлы, а конечные узлы содержат ссылки на данные на диске.

Фу!

Answer 2

Полагаю, я ответил на этот вопрос в главе 1 моего учебника по индексированию SQL: http://use -the-index-luke.com / sql / anatomy

Подводя итог наиболее важным частям, касающимся вашего конкретного вопроса:

- из "Листовых Узлов"

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

- из "The B-Tree":

Листовые узлы индекса хранятся в произвольном порядке - положение на диск не соответствует логической позиции в соответствии с порядок индекса. Это как телефонный справочник с перемешанными страницами. Если вы ищете «Смит» в, но откройте его в «Робинсон» в первом место, ни в коем случае не считается, что Смит возвращается дальше. Базы данных нуждаются во второй структуре, чтобы быстро найти запись среди перетасованные страницы: сбалансированное дерево поиска - короче: B-Tree.

Answer 3

Связанные списки обычно упорядочены не по значению ключа, а к моменту вставки: вставка выполняется в конце списка, и каждая новая запись содержит указатель на предыдущую запись списка.

Они обычно реализуются как структуры кучи.

Это имеет 2 основных преимущества:

• ими очень легко управлять (вам нужен указатель для каждого элемента)

• при использовании в сочетании с индексом вы можете решить проблему последовательного доступа.

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

B + деревья - это лучшие структуры, обладающие всеми указанными вами свойствами и другими преимуществами:

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

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

• эти структуры очень эффективны при операциях обновления, вставки или удаления.