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

Время поиска в отсортированном файле

Обычно алгоритмы сортировки и поиска характеризуются количеством операций сравнения, которые должны быть выполнены с использованием нотации порядка. Двоичный поиск в отсортированной таблице с N записями, например, может быть выполнен примерно за ⌈ log 2 N ⌉ сравнений. Если бы в таблице был 1 000 000 записей, то конкретная запись могла бы быть обнаружена не более чем с 20 сравнениями: ⌈ log 2 (1 000 000) ⌉ = 20.

Исторически большие базы данных хранились на жестких дисках. Время чтения записи на диске намного превышает время, необходимое для сравнения ключей, когда запись доступна. Время чтения записи с диска включает в себя время поиска и задержку вращения. Время поиска может составлять от 0 до 20 или более миллисекунд, а задержка вращения составляет в среднем около половины периода вращения. Для привода на 7200 об./мин период вращения составляет 8,33 миллисекунды. Для накопителя, такого как Seagate ST3500320NS, время поиска между дорожками составляет 0,8 мс, а среднее время поиска при чтении — 8,5 мс. Для простоты предположим, что чтение с диска занимает около 10 миллисекунд.

Тогда, чтобы найти одну запись из миллиона, потребовалось бы 20 операций чтения с диска по 10 миллисекунд, что составляет 0,2 секунды.

Можно избежать проблем со временем, если отдельные записи будут сгруппированы вместе в дисковом блоке. Дисковые блоки могут быть по 16 килобайт. Если каждая запись имеет размер 160 байт, то в каждом блоке может храниться 100 записей. Вышеупомянутое время чтения с диска фактически относится к целому блоку. Как только головка диска начинает находиться в нужном положении, один или несколько блоков диска могут быть прочитаны с небольшой задержкой. При 100 записях в блоке последние 6 или около того сравнений не требуют каких-либо операций чтения с диска — все сравнения выполняются в последнем считанном блоке диска.

Для дальнейшего ускорения поиска необходимо ускорить первые 13–14 сравнений (каждое из которых требует доступ к диску).

Индекс ускоряет поиск

Индекс B-Tree создает многоуровневую древовидную структуру, которая разбивает базу данных на блоки или страницы фиксированного размера. Каждый уровень этого дерева может использоваться для связывания этих страниц через расположение адреса, позволяя одной странице (известной как узел или внутренняя страница) ссылаться на другую с конечными страницами на самом низком уровне. Одна страница обычно является отправной точкой дерева или «корнем». Именно здесь начнется поиск определенного ключа, проходя по пути, который заканчивается листом. Большинство страниц в этой структуре будут конечными страницами, которые в итоге ссылаются на определенные строки таблицы.

Значительного улучшения производительности можно добиться с помощью индекса B-Tree. Поскольку каждый узел (или внутренняя страница) может иметь более двух дочерних элементов, индекс B-дерева обычно имеет меньшую высоту (расстояние от корня до самого дальнего листа), чем двоичное дерево поиска. В приведенном выше примере начальные чтения с диска сузили диапазон поиска в два раза. Это можно существенно улучшить, создав вспомогательный индекс, содержащий первую запись в каждом блоке диска (иногда называемый разреженным индексом). Этот вспомогательный индекс будет составлять 1% от размера исходной базы данных, но поиск по нему будет выполняться быстрее. Поиск записи во вспомогательном указателе подскажет нам, в каком блоке искать в основной базе данных; после поиска во вспомогательном индексе нам пришлось бы искать только в этом одном блоке основной базы данных — за счет еще одного чтения с диска. Индекс будет содержать 10 000 записей, поэтому потребуется не более 14 сравнений. Как и в основной базе данных, последние шесть или около того сравнений во вспомогательном индексе будут находиться в одном и том же блоке диска. Индекс можно было найти примерно за восемь чтений с диска, а доступ к нужной записи можно было получить за 9 чтений с диска.

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

Вместо того чтобы читать 14 блоков диска для поиска нужной записи, нам нужно прочитать только 3 блока. Эта блокировка является основной идеей создания B-Tree, где блоки диска заполняют иерархию уровней, составляющих индекс. Чтение и поиск первого (и единственного) блока вспомогательного индекса, который является корнем дерева, идентифицирует соответствующий блок вспомогательного индекса на уровне ниже. Чтение и поиск этого вспомогательного индексного блока идентифицирует соответствующий блок для чтения, пока последний уровень, известный как конечный уровень, не идентифицирует запись в основной базе данных. Вместо 150 миллисекунд нам нужно всего 30 миллисекунд, чтобы получить запись.

Вспомогательные индексы превратили задачу поиска из бинарного поиска, требующего примерно log 2 N операций чтения с диска, в задачу, требующую только log b N операций чтения с диска, где b — коэффициент блокировки (количество записей в блоке: b = 100 записей в блоке в нашей пример; log 100 1 000 000 = 3 чтения).

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

Вставки и удаления

Если база данных не меняется, то составить индекс несложно. Его никогда не нужно менять. Если же будут изменения, то управление базой данных и ее индексом усложняется.

Удалить записи из базы данных относительно просто. Индекс может остаться прежним, а запись можно просто пометить как удаленную. База данных остается в отсортированном порядке. Если есть большое количество ленивых удалений, то поиск и хранение становятся менее эффективными.

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

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

Преимущества использования B-Tree для баз данных

B-Tree использует все идеи, описанные выше. В частности B-Tree:

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

Кроме того, B-Tree минимизирует потери, гарантируя, что внутренние узлы заполнены как минимум наполовину. B-Tree может обрабатывать произвольное количество вставок и удалений.

О__ригинал статьи ты можешь найти по ссылке.

Также рекомендуем ознакомиться с дополнительным источником.