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

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

Обычно алгоритмы сортировки и поиска характеризуются количеством операций сравнения, которые должны быть выполнены с использованием записи порядка. Например, двоичный поиск отсортированной таблицы с N записями может быть выполнен примерно в log2 N сравнениях. Если в таблице содержится 1 000 000 записей, то конкретная запись может быть найдена не более чем в 20 сравнениях: log2 (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 сравнений (каждое из которых требовало доступа к диску).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поиск по этому блогу

Alex tools