Два дня назад друг пригласил меня ответить на вопрос,Почему MongoDB (индекс) использует B-деревья, а Mysql использует B+деревья?Я думаю, что этот вопрос очень хорош, нет лучшего способа изучить структуры данных с точки зрения практического применения. Поскольку большие и надежные программы, такие как Mysql и MongoDB, предназначены для усовершенствования, почему они выбрали именно эти структуры данных? :)
В этой статье представлены и проанализированы B-деревья и B+ деревья с точки зрения практического применения.
Происхождение B-дерева
Определение: B-дерево — это разновидность дерева, включая B-дерево, B+ дерево, B* дерево и т. д. Это самобалансирующееся дерево поиска, похожее на обычное сбалансированное бинарное дерево, разница в том, что B-дерево позволяет каждому узлу иметьбольше дочерних узлов. B-дерево специально разработано для внешнего хранилища, например диска, имеет хорошую производительность при чтении и записи больших блоков данных, поэтому обычно используется в файловых системах и базах данных.
В определении просто нужно знать, что B-деревья позволяют каждому узлу иметь больше потомков. Количество дочерних узлов обычно исчисляется тысячами, и конкретное число зависит от характеристик внешней памяти.
Давайте сначала посмотрим, почему появляются структуры данных, такие как B-деревья.
Традиционное балансное двоичное дерево, используемое для поиска много, например, деревьев AVL, Red-Happe и т. Д. Эти деревья очень хороши в общем порядке расследования, но они будут сильны, когда данные очень велики. Причина в том, что объем данных очень большой, а память недостаточно. Большинство данных можно сохранить только на диске, и только необходимые данные загружаются в память. В общем, доступ памяти имеет время около 50 нс, а диск составляет около 10 мс. Скорость аналогична почти 5 заказам, и дисковое время чтения далеко превышает время данных по сравнению с памятью. Это показывает, что большая часть программы заблокирует на диске IO. Итак, как мы улучшаем производительность программы?Сокращение времени дискового ввода-вывода,рисунок
Сбалансированные двоичные деревья, такие как деревья AVL и красно-черные деревья, не могут «обслуживать» диск по своей конструкции.
Обратитесь к дискуГоворя о модели хранения в компьютере (4) Диск
На приведенном выше рисунке показано простое сбалансированное двоичное дерево.Сбалансированное двоичное дерево создается с помощьювращатьсохранять равновесие,в то время как вращение - это операция на всем дереве, операция вращения не может быть завершена, если ее часть загружена в память. Во-вторых, высота сбалансированного бинарного дерева относительно велика как log n (основание равно 2), поэтому логически близкие узлы могут быть на самом деле очень далеко, а упреждающее чтение с диска (принцип локальности) не может быть эффективно использовано, поэтому такое сбалансированное бинарное дерево используется в базе данных, и выбор в файловой системе передается.
Принцип пространственной локальности: если доступ к месту в памяти осуществляется, то и место рядом с ним также будет доступно.
Давайте посмотрим на проектирование B-деревьев с точки зрения «обслуживания» диска.
Эффективность индексации зависит от количества дисковых операций ввода-вывода.Быстрая индексация должна эффективно сокращать количество дисковых операций ввода-вывода.Как быстро индексировать? Принцип индексации на самом делеПродолжайте сужать область поиска, точно так же, как мы обычно используем словарь для поиска слов, сначала находим первую букву, чтобы сузить область, затем вторую букву и так далее. Сбалансированное бинарное дерево делит диапазон сразу на два интервала. быть быстрее,B-дерево каждый раз делит диапазон на несколько интервалов.Чем больше интервалов, тем быстрее и точнее данные позиционирования.. Затем, если узел представляет собой диапазон интервалов, каждый узел больше. Поэтому при создании новой ноды напрямую обращайтесь за пространством размера страницы (диск разделен по блокам, обычно 512 Байт. Дисковый ввод-вывод считывает несколько блоков за раз, мы называем это страницей, конкретный размер зависит от операционной системы, обычно 4 КБ, 8 КБ или 16 КБ), выделение памяти компьютера выравнивается по страницам, так что только узел Требуется один IO.
На приведенном выше рисунке представлено упрощенное B-дерево. Преимущества множественной вилки очень очевидны. Оно эффективно уменьшает высоту B-дерева, которая равна log n с большим основанием. Размер основания связан с числом дочерних узлов узла.Как правило, B-дерево -высота дерева составляет около 3 этажей. Чем меньше количество слоев, тем точнее диапазон, определяемый областью каждого узла, и тем быстрее диапазон уменьшается. Как упоминалось выше, узлу необходимо выполнить один ввод-вывод, поэтому общее количество операций ввода-вывода сокращается до log n раз. Каждый узел B-дерева представляет собой упорядоченную последовательность из n (a1, a2, a3...an), а дочерние узлы узла разбиты на n+1 интервалов для индексации (X1 an).
B-дерево
На картинке выше изображено B-дерево,Каждый узел B-дерева имеет d~2d ключей.,2Этот фактор определяет правила разделения и слияния деревьев, поддерживающие баланс B-дерева.
Вставка и удаление B-деревьев подробно не представлены, и во многих материалах описан этот процесс. В обычном сбалансированном бинарном дереве, если условие баланса не выполняется после вставки и удаления,вращатьоперации, в то время как в B-дереве операции разделения и слияния выполняются, если условия не выполняются после вставки и удаления.
Кратко опишите операции разделения и слияния.
Разделение: если есть узел с 2d ключами, после добавления одного это будет 2d+1 ключ, что не соответствует приведенным выше правилам.Каждый узел B-дерева имеет d ~ 2d ключей, больше 2d., затем разделите узел на два узла с ключами d и верните срединный ключ родительскому узлу.
Слияние: если есть узел с d ключами, это будет d-1 ключ после удаления одного, который не соответствует вышеуказанным правилам.Каждый узел B-дерева имеет d~2d ключей, меньше чем d, то узлы объединяются.После слияния, если условия выполняются, слияние завершается.Если нет, то узлы разбиваются на два узла.
поиск B-дерева
Давайте посмотрим на B-деревонайти, предполагая, что каждый узел имеет n значений ключа, которые разделены на n+1 интервалов, обратите внимание, чтоЗа каждым значением ключа сразу же следует поле данных, что означает, что ключ и данные B-дерева объединяются вместе.. Вообще говоря, все корневые узлы находятся в памяти, и B-дерево использует каждый узел как дисковый ввод-вывод.Например, на приведенном выше рисунке, если вы ищете данные с ключом из 25 узлов, сначала выполните двоичный поиск на корневой узел (поскольку ключи упорядочены, две точки являются самыми быстрыми), полагая, что ключ 25 меньше, чем ключ 50, поэтому найдите самый левый узел,Сделайте дисковый ввод-вывод в этот момент, прочитайте узел с диска в память и продолжайте описанный выше процесс, пока узел не будет найден. ключ вверх.
Найти псевдокод
Data* BTreeSearch(Root *node, Key key)
{
Data* data;
if(root == NULL)
return NULL;
data = BinarySearch(node);
if(data->key == key)
{
return data;
}else{
node = ReadDisk(data->next);
BTreeSearch(node, key);
}
}В+ дерево
B+-дерево является вариантом B-дерева, отличается от B-дерева тем, что:
- В дереве B+ копия ключа хранится на внутренних узлах, а реальный ключ и данные хранятся на листовых узлах..
- Поле указателя узла для n значений ключа равно n вместо n+1.
На следующем рисунке показано дерево B+:
Поскольку внутренний узел не хранит данные, узел листьев дерева B + отличается в целом, а каждый размер узла B-дерева обычно одинаково.
чтобы увеличитьИнтервальная доступность, и вообще сделать некоторые оптимизации дерева B+.
На следующем рисунке показано дерево B+ с последовательным доступом.
Разница между B-деревом и B+ деревом
1. Узлы в дереве B+ не хранят данные, и все данные хранятся в листовых узлах, что приводит к фиксированной временной сложности запроса log n. Временная сложность запроса B-дерева не фиксирована, она связана с положением ключа в дереве, предпочтительно O(1).
Как показано ниже, данные запроса B-дерева/B+ дерева, ключ узла которых равен 50.
B-дерево
Как видно из рисунка выше, узел с ключом 50 находится на первом слое, а для завершения поиска B-дереву требуется только один дисковый ввод-вывод. Таким образом, наилучшая временная сложность запроса B-дереваO(1).
В+ дерево
Поскольку все поля данных дерева B+ находятся в корневом узле, узел, ключ запроса которого равен 50, должен быть проиндексирован от корневого узла к конечному узлу, а временная сложность фиксируется какO(log n).
2. The connection of B+ leaf nodes can greatly increase the accessibility of the interval, which can be used in range queries, etc., while the key and data of each node of the B-tree are together, and the interval search cannot be выполненный..
В соответствии с принципом пространственной локальности: если осуществляется доступ к месту в памяти, то и место рядом с ним также будет доступно.
Дерево B+ может хорошо использовать принцип локальности. Если мы получим доступ к ключу узла 50, в будущем также могут быть доступны узлы с ключами 55, 60 и 62. Мы можемИспользуйте принцип упреждающего чтения с диска, чтобы заблаговременно считывать эти данные в память, уменьшая количество дисковых операций ввода-вывода..
Конечно, деревья B+ также могут хорошо выполнять запросы диапазона. Например, запросите узлы, значение ключа которых находится в диапазоне 50-70.
Дерево 3.B+ больше подходит для внешнего хранилища. Поскольку внутренний узел не имеет поля данных, диапазон, который может индексировать каждый узел, больше и точнее.
Это легко понять, потому что каждый ключ внутри узла B-дерева несет в себе поле данных, в то время как узел дерева B+ хранит только копию ключа, а настоящий ключ и поля данных хранятся в листовых узлах. Как упоминалось ранее, диск разделен на блоки, и дисковый ввод-вывод будет считывать несколько блоков, что связано с операционной системой.Поскольку размер данных дискового ввода-вывода фиксирован, в одном вводе-выводе,Чем меньше один элемент, тем больше сумма. это означаетОбъем информации на одном дисковом вводе-выводе дерева B+ больше, чем у B-дерева., с этой точки зрения количество дисковых операций ввода-вывода дерева B+ меньше, чем у дерева B.
Из рисунка выше видно, что для одного и того же размера области B-дерево имеет только 2 ключа, а B+ дерево имеет 3 ключа.
Почему индексы MongoDB выбирают B-деревья, а индексы Mysql выбирают деревья B+
Поняв это, давайте посмотримПочему индекс MongoDB выбирает B-дерево, а индекс Mysql (движок InooDB) выбирает дерево B+.
Mysql должен быть знаком каждому, ниже представлена традиционная реляционная база данных MongoDB.
Взгляните на определение MongoDB в Википедии:
MongoDB (from humongous) is a cross-platform document-oriented database. Classified as a NoSQL database, MongoDB eschews the traditional table-based relational database structure in favor of JSON-like documents with dynamic schemas (MongoDB calls the format BSON)
Общий смысл этого отрывка заключается в том, что Mongodb является базой данных типа документов, своего рода NoSQL, которая использует JSON-формат для сохранения данных.
Базы данных документов отличаются от наших обычных реляционных баз данных, обычно использующих формат XML или Json для сохранения данных, принадлежащихАгрегированная база данных.
Базы данных типа «ключ-значение» также являются агрегированными базами данных, и те, кто знаком с Redis, должны хорошо их понимать.
Например:
Присоединяйтесь к нам, чтобы создать веб-сайт электронной коммерции, аналогичный Taobao, который продает продукты пользователям, поэтому он должен хранить информацию о пользователях, каталоги продуктов, заказы, адреса доставки, адреса для выставления счетов, способы оплаты и т. д.
Посмотрите, как хранится традиционная реляционная база данных:
Совокупная модель хранения базы данных:
Представлено в формате, подобном Json, следующим образом:
//Customer
{
"id":1,
"name":Tom,
"billingAddress":[{"city":"China"}]
}
//Orders
{
"id":99,
"orderItem":[
"productId"27,
"price":100,
"productName":book
],
"shippingAddress":[{"city":"china"}],
"orderPayment":[
...
]
}По сравнению с реляционными базами данных Mysql, nosql, такой как MongoDB, подходит дляПростая модель данных и высокие требования к производительности
Почему MongoDB использует B-деревья
MongoDB — это nosql, также хранящийся на диске и предназначенный для использования вПростая модель данных и высокие требования к производительности. Высокие требования к производительности, обратите внимание на первый пункт отличия деревьев B/B+:
Узлы в дереве B+ не хранят данные, и все данные хранятся в листовых узлах, что приводит к фиксированной временной сложности запроса log n. Временная сложность запроса B-дерева не фиксирована, она связана с положением ключа в дереве, предпочтительно O(1)
Мы говорили, что как можно меньше дисковых операций ввода-вывода является эффективным средством повышения производительности. MongoDB — это совокупная база данных, иВ B-дереве ключи и поля данных объединены вместе..
Почему Mysql использует дерево B+
Mysql — реляционная база данных, и интервальный доступ — обычная ситуация, в то время как B-tree не поддерживает интервальный доступ (см. рисунок выше), иПоскольку все данные B+-дерева хранятся в листовых узлах и связаны друг с другом указателями, легко выполнить интервальный обход или даже полный обход.. См. второй пункт различия между деревьями B/B+:
Соединение листовых B+ узлов может значительно повысить доступность интервала, что можно использовать в запросах диапазона и т.п., при этом ключ и данные каждого узла B-дерева находятся вместе, и поиск по интервалу не может быть выполнен..
Во-вторых, эффективность запросов дерева B+ более стабильна, все данные хранятся в листовых узлах, а временная сложность запроса фиксируется какO(log n).
Последний третий пункт:
Деревья B+ больше подходят для внешнего хранилища. Поскольку внутренний узел не имеет поля данных, диапазон, который может индексировать каждый узел, больше и точнее.
В конце этой статьи, если есть какие-либо ошибки, пожалуйста, поправьте меня :)
——от группы XiyouLinux Автор: wwh