Когда мы думаем о производительности базы данных, первое, что приходит в голову, - это индексирование. Здесь мы собираемся изучить, как индексация базы данных работает с базой данных. Обратите внимание, что здесь архитектурные детали описаны на основе архитектуры базы данных SQLite 2.x. Вы можете найти внутреннюю реализацию SQLite 2.5.0, имеющую отношение к этому блогу, в https://github.com/madushadhanushka/simple-sqlite вместе с примерами тестов.
Что такое Btree?
Btree - это структура данных, которая хранит данные в своем узле в отсортированном порядке. Мы можем представить образец Btree следующим образом.
Btree хранит данные таким образом, что каждый узел содержит ключи в возрастающем порядке. Каждый из этих ключей имеет две ссылки на два других дочерних узла. Ключи левого дочернего узла меньше, чем текущий ключ, а ключи правого дочернего узла больше, чем текущий ключ. Если один узел имеет «n» ключей, то он может иметь максимум «n + 1» дочерних узлов.
Почему индексация используется в базе данных?
Считайте, что вам нужно сохранить список чисел в файле и выполнить поиск по заданному номеру в этом списке. Самое простое решение - хранить данные в массиве и добавлять значения, когда приходит новое значение. Но, если вам нужно проверить, существует ли данное значение в массиве, вам нужно выполнить поиск по всем элементам массива один за другим и проверить, существует ли данное значение. Если вам повезет, вы можете найти данное значение в первом элементе. В худшем случае значение может быть последним элементом массива. Мы можем обозначить этот худший случай как O (n) в асимптотической записи. это означает, что если размер вашего массива не больше «n», вам нужно выполнить «n» поисков, чтобы найти заданное значение в массиве.
Как можно сократить время поиска? Самое простое решение - отсортировать массив и использовать двоичный поиск для поиска значения. Всякий раз, когда вы вставляете значение в массив, оно должно поддерживать порядок. Поиск начинается с выбора значения из середины массива. Затем сравните выбранное значение с поисковым значением. Если выбранное значение больше, чем значение поиска, игнорируйте левую часть массива и значение поиска справа, и наоборот.
Здесь мы пытаемся найти ключ 15 из массива 3,6,8,11,15,18 и 18, который уже находится в отсортированном порядке. Если вы выполните обычный поиск, то поиск займет пять единиц времени, начиная с элемента в пятой позиции. Но в бинарном поиске потребуется всего три поиска.
Если мы применим этот двоичный поиск ко всем элементам в массиве, то это будет следующим образом.
Знакомо? Это B внутреннее дерево. Это простейшие формы Btree. Для двоичного дерева мы можем использовать указатели вместо хранения данных в отсортированном массиве. Математически мы можем доказать, что время поиска для двоичного дерева в худшем случае равно O (log (n)). Концепция двоичного дерева может быть расширена до более обобщенной формы, известной как Btree. Вместо того, чтобы иметь одну запись для одного узла, Btree использует массив записей для одного узла и имеет ссылку на дочерний узел для каждой из этих записей. Ниже приводится сравнение временной сложности каждого из описанных ранее методов.
┌────────────────┬───────────┬────────────┬───────────┐ │ Type │ Insertion │ Deletion │ Lookup │ ├────────────────┼───────────┼────────────┼───────────┤ │ Unsorted Array │ O(1) │ O(n) │ O(n) │ │ Sorted Array │ O(n) │ O(n) │ O(log(n)) │ │ Btree │ O(log(n)) │ O(log(n))) │ O(log(n)) │ └────────────────┴───────────┴────────────┴───────────┘
B + tree - это еще одна структура данных, которая используется для хранения данных, которая выглядит почти так же, как Btree. Единственное отличие B + tree состоит в том, что оно хранит данные на листовых узлах. Это означает, что все значения нелистовых узлов снова дублируются в листовых узлах. Ниже приведено примерное дерево B +.
Здесь 13, 30, 9, 11, 16, 38 нелистовых значений снова повторяются в конечных узлах. Можете ли вы увидеть особенности этого дерева в листовых узлах?
Да, листовой узел включает все значения, и все записи отсортированы. В специальности B + tree вы можете выполнять поиск так же, как Btree, и, кроме того, вы можете перемещаться по всем значениям в листовом узле, если мы поместим указатель на каждый листовой узел следующим образом.
Как индексация используется в базе данных?
Когда Btree приходит к индексации базы данных, эта структура данных немного усложняется не только из-за наличия ключа, но и из-за наличия значения, связанного с ключом. это значение является ссылкой на фактическую запись данных. Этот ключ и значение вместе называются полезной нагрузкой.
Предположим, что следующие три столбца таблицы необходимо сохранить в базе данных.
┌───────┬───────┬─────┐ │ Name │ Marks │ Age │ ├───────┼───────┼─────┤ │ Jone │ 5 │ 28 │ │ Alex │ 32 │ 45 │ │ Tom │ 37 │ 23 │ │ Ron │ 87 │ 13 │ │ Mark │ 20 │ 48 │ │ Bob │ 89 │ 32 │ └───────┴───────┴─────┘
Сначала база данных создает уникальный случайный индекс (или первичный ключ) для каждой данной записи и преобразует соответствующие строки в поток байтов. Затем он сохраняет каждый из ключей и записывает поток байтов в дереве B +. Здесь случайный индекс, используемый в качестве ключа для индексации. Ключ и поток байтов записи вместе известны как Payload. Результирующее B + дерево можно представить следующим образом.
Здесь вы можете видеть, что все записи хранятся в конечных узлах дерева B +, а индекс используется в качестве ключа для создания дерева B +. На нелистовых узлах записи не хранятся. Каждый из листовых узлов имеет ссылку на следующую запись в дереве. База данных может выполнять двоичный поиск с использованием индекса или последовательного поиска, просматривая каждый элемент, путешествуя только через листовые узлы.
Если индексация не используется, тогда база данных прочитает каждую из этих записей, чтобы найти данную запись. При включенном индексировании база данных создает три B-дерева для каждого столбца в таблице, как показано ниже. Здесь ключ - это ключ Btree, используемый для индексации. Индекс - это ссылка на фактическую запись данных.
Когда используется индексирование First, база данных выполняет поиск по заданному ключу в соответствующем Btree и получает индекс за время O (log (n)). Затем он выполняет еще один поиск в дереве B +, используя уже найденный индекс за время O (log (n)), и получает запись.
Реализация страниц базы данных
Каждый из этих узлов в Btree и B + tree хранится внутри Pages. Страницы имеют фиксированный размер. Страницы имеют уникальный номер, начинающийся с единицы. Страница может быть ссылкой на другую страницу с помощью номера страницы. В начале страницы хранятся метаданные страницы, такие как номер самой правой дочерней страницы, смещение первой свободной ячейки и смещение первой ячейки. В базе данных может быть два типа страниц.
- Страницы для индексации: на этих страницах хранится только индекс и ссылка на другую страницу.
- Страницы для хранения записей: на этих страницах хранятся фактические данные, и страница должна быть листовой.
Заключение
Базы данных должны иметь эффективный способ хранения, чтения и изменения данных. Btree обеспечивает эффективный способ вставки и чтения данных. В реальной реализации базы данных база данных использует вместе как Btree, так и B + tree для хранения данных. Btree используется для индексации, а дерево B + используется для хранения фактических записей. Дерево B + обеспечивает возможность последовательного поиска в дополнение к двоичному поиску, что дает базе данных больше контроля для поиска неиндексных значений в базе данных.
