Понимание индексов B + tree и их влияния на производительность

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

B + древовидные индексы

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

Дерево B + может иметь более 1 ключа в узле, на самом деле тысячи ключей обычно хранятся в узле, и, следовательно, коэффициент ветвления дерева B + очень велик, что позволяет деревьям B + быть много мельче по сравнению с их аналогами в двоичном дереве поиска.
Деревья B + имеют все ключевые значения в своих листовых узлах. Все листовые узлы B + -дерева находятся на одной высоте, что означает, что каждый поиск по индексу потребует одинакового количества поисков по B +-дереву, чтобы найти значение.
В дереве B + все конечные узлы связаны друг с другом в связанном списке слева направо, а поскольку значения на конечных узлах отсортированы, поиск по диапазонам очень эффективен.

Типичное B + дерево

Ниже приведено типичное дерево B +:

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

Зачем использовать B + tree?

B + tree используется по очевидной причине - скорости. Как мы знаем, когда речь идет о памяти, существуют ограничения по пространству, и не все данные могут находиться в памяти, и, следовательно, большую часть данных необходимо сохранять на диске. Диск, как мы знаем, намного медленнее по сравнению с памятью, потому что у него есть движущиеся части. Таким образом, если бы не было древовидной структуры для поиска, то чтобы найти значение в базе данных, СУБД должна была бы выполнить последовательное сканирование всех записей. Теперь представьте размер данных в миллиард строк, и вы можете ясно увидеть, что последовательное сканирование займет очень много времени.
Но с деревом B + можно сохранить миллиард ключевых значений (с указателями на миллиардов строк) на высоте 3, 4 или 5, так что каждый поиск ключа из миллиарда ключей потребует 3, 4 или 5 обращений к диску, что является огромной экономией.

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

Как устроено дерево B +?

Деревья B + обычно структурированы таким образом, что размер узла выбирается в соответствии с размером страницы. Почему? Поскольку всякий раз, когда осуществляется доступ к данным на диске, вместо чтения нескольких битов читается вся страница данных, потому что это намного дешевле.
Давайте посмотрим на пример,
Рассмотрим InnoDB, размер страницы которого равен 16 КБ, и предположим, что у нас есть индекс для целочисленного столбца размером 4 байта, поэтому узел может содержать не более 16 * 1024/4 = 4096 ключей, а узел может иметь не более 4097 дочерних элементов. .
Итак, для дерева B + высотой 1 корневой узел имеет 4096 ключей, а узлы на высоте 1 (конечные узлы) имеют 4096 * 4097 = 16781312 значений ключей.
Это свидетельствует об эффективности индекса дерева B +, более 16 миллионов значений ключей могут быть сохранены в дереве B + с высотой 1 и каждым значением ключа можно получить ровно за два запроса.

Насколько важен размер значений индекса?

Как видно из приведенного выше примера, размер значений индекса играет очень важную роль по следующим причинам:

Чем длиннее индекс, тем меньшее количество значений может поместиться в узле и, следовательно, тем больше высота дерева B +.
Чем больше высота дерева, тем больше требуется обращений к диску.
Чем больше доступ к диску, тем меньше производительность.

Таким образом, размер значений индекса имеет прямое отношение к производительности!

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

Первоначально опубликовано на www.ovaistariq.net.