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

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

1. Что такое индекс базы данных? Словарь Синьхуа вам в помощь-- понимать

2. Интеграция индекса базы данных- глубоко

3. 20-минутная практика проектирования индекса базы данных- бой

4. Почему индекс базы данных реализован с деревом B+?- расширение

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

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

Вы, должно быть, слышали пример на уроке математики: лучший способ найти конкретное число в куче отсортированных чисел — это метод, называемый «двоичным поиском». Конкретный процесс заключается в том, чтобы сначала найти число в середине этих чисел, а затем сравнить, является ли целевое число больше или меньше этого числа, а затем продолжить поиск в первой или второй половине чисел в соответствии с результатом. .

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

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

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

иерархия памяти компьютера

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

Те, у кого есть опыт программирования, знают, что работа программы в основном связана с памятью, а для доступа к данным во внешней памяти часто требуется запись некоторого файла для чтения и записи кода. Это происходит именно потому, что скорость вычислений ЦП намного выше, чем скорость ввода/вывода (скорость ввода/вывода) хранилища.Поскольку ЦП должен ждать ввода следующего пакета данных после завершения каждого вычисления, это время ожидания Чем оно короче, тем быстрее работает компьютер.

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

Если вы не знакомы с B+ деревом, вы можете найти ответ в этой статье -Интеграция индекса базы данных.

Если рассматривать бинарное дерево как особое B+-дерево (B+-дерево только с одним значением и двумя указателями до и после каждого узла), то можно сделать вывод: ** Поскольку количество значений, содержащихся в узлах B+ дерево (больше значений), чем бинарное дерево (1 значение), поэтому для запроса дерева B+ требуется меньше узлов. **Тогда, если стоимость чтения одинакова, потому что总成本=读取次数*单次读取成本, мы можем доказать, что стоимость запроса B+ дерева намного меньше, чем у бинарного дерева.

Стоимость чтения узла

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

В современных операционных системах единица, используемая для чтения данных из внешней памяти в память, обычно называется «страницей».Каждый раз при чтении данных необходимо считывать целое число «страниц», а не половину страницы или 0,8 страницы. Размер страницы определяется операционной системой, и обычно размер страницы составляет 4 КБ = 4096 байт. Итак, хотим ли мы прочитать 1 байт или 2 КБ, в конце нам нужно прочитать полную страницу размером 4 КБ, тогда стоимость чтения узла зависит от количества страниц, которые необходимо прочитать.

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

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