Почему MongoDB использует B-Tree, а Mysql использует B+Tree?

В дополнение к дереву B+ вы, возможно, слышали о дереве B и дереве B-. На самом деле дерево B- — это дерево B. Английский перевод — дерево B. «-» здесь не « +" в относительном дереве B+. , а просто соединитель. B-дерево на самом деле представляет собой низкоуровневую версию B+-дерева, или B+-дерево — улучшенную версию B-дерева.

B+ tree

Дерево B+ на самом деле является m-разветвленным сбалансированным деревом поиска (не бинарным деревом).

Определение сбалансированного дерева поиска: разница в высоте между левым и правым поддеревьями любого узла в дереве не может быть больше 1

/**
* 这是B+树非叶子节点的定义。
*
* 假设keywords=[3, 5, 8, 10]
* 4个键值将数据分为5个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
* 5个区间分别对应：children[0]...children[4]
*
* m值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
*/
public class BPlusTreeNode {
  // 5叉树
  public static int m = 5;

  // 键值，用来划分数据区间
  public int[] keywords = new int[m-1];

  // 保存子节点指针
  public BPlusTreeNode[] children = new BPlusTreeNode[m];
}
/**
* 这是B+树中叶子节点的定义。
*
* B+树中的叶子节点跟内部结点是不一样的,
* 叶子节点存储的是值，而非区间。
* 这个定义里，每个叶子节点存储3个数据行的键值及地址信息。
*
* k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
* PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
*/
public class BPlusTreeLeafNode {
  public static int k = 3;

  // 数据的键值
  public int[] keywords = new int[k];

  // 数据地址
  public long[] dataAddress = new long[k];

  // 这个结点在链表中的前驱结点
  public BPlusTreeLeafNode prev;

  // 这个结点在链表中的后继结点 
  public BPlusTreeLeafNode next;
}

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

Подводя итог, дерево B+ имеет следующие характеристики.

Каждый узел дерева B+ может содержать больше узлов, на это есть две причины: одна — уменьшить высоту дерева (индекс не весь будет храниться в памяти, и память может не удержать его, поэтому дерево индексов обычно хранится на диске, просто поместите корневой узел в память, чтобы доступ к каждому узлу фактически осуществлял доступ к диску, высота дерева равна количеству дисковых операций ввода-вывода каждый раз, когда запрашиваются данные), другой — диапазон данных изменен на несколько интервалов. Чем больше интервал, тем быстрее извлечение данных (можно представить пропуск таблицы)
Вместо того, чтобы хранить один ключ, каждый узел хранит несколько ключей.
Листовые узлы используются для хранения данных, а другие узлы используются для индексации.
Конечные узлы связаны друг с другом через два указателя, и производительность последовательных запросов выше.

Эта конструкция также имеет следующие преимущества:

Неконечные узлы дерева B+ хранят только ключи и занимают очень мало места, поэтому каждый уровень узла может индексировать гораздо более широкий диапазон данных. Другими словами, для каждой операции ввода-вывода можно искать больше данных.
Конечные узлы соединены парами, что соответствует функции упреждающего чтения дисков. Например, конечные узлы хранят 50 и 55, которые имеют указатели на конечные узлы 60 и 62. Когда мы читаем с диска данные, соответствующие 50 и 55, мы будем упоминать 60 и 62 мимоходом из-за характера диска с упреждающим чтением. Прочтите соответствующие данные. На этот раз последовательное чтение, а не поиск по диску, ускоряет процесс.
Поддержка запроса диапазона, запрос локального диапазона очень эффективен, каждый узел может индексировать больший и более точный диапазон, что означает, что информация о вводе-выводе на один диск в дереве B+ больше, чем в дереве B, а эффективность ввода-вывода выше.
Поскольку данные хранятся на уровне листовых узлов и имеются указатели на другие конечные узлы, запросы диапазона должны проходить только слой конечных узлов, а не все дерево.

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

Чтобы узнать, как реализована индексация данных MySQL, вы можете обратиться к этой статье:time.geekgang.org/column/arity…

B-Tree

B-Tree на самом деле является сбалансированным деревом поиска m-fork.

Все ключевые значения распределены по всему дереву
Все ключевые значения появляются в одном узле
Поиск может заканчиваться на нелистовых узлах
При полном поиске по ключевым словам производительность близка к бинарному поиску.

Разница между B-деревом и деревом B+

Неконечные узлы в дереве B+ не хранят данные, а все данные, хранящиеся в конечных узлах, делают временную сложность запроса фиксированной и равной log n.
Сложность времени запроса B-дерева не фиксирована, она связана с положением ключа в дереве, предпочтительно O(1).
Поскольку узлы листьев дерева B + связаны через вдвойне связанный список, поддерживаются запросы диапазона, а эффективность выше, чем у дерева B.
B-дерево каждый узел и ключевые данные вместе

Почему MongoDB использует B-Tree, а Mysql использует B+Tree?

Неконечные узлы в дереве B+ не хранят данные, а все данные, хранящиеся в конечных узлах, делают временную сложность запроса фиксированной и равной log n. Временная сложность запроса B-дерева не фиксирована, она связана с положением ключа в дереве, предпочтительно O(1).

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

Что касается того, почему MongoDB использует B-деревья вместо B+-деревьев, это можно рассматривать с точки зрения его дизайна. MongoDB — это не традиционная реляционная база данных, а nosql, хранящийся в формате BSON (например, JSON). Целью является высокая производительность, высокая доступность и простота масштабирования.

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

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

Хэш-индекс

Короче говоря, хэш-индекс использует некоторый алгоритм хеширования для преобразования значения ключа в новое значение хеш-функции. Нет необходимости выполнять пошаговый поиск от корневого узла к конечному узлу, как в дереве B+. Нужен только один хеш-алгоритм, и соответствующую позицию можно найти сразу, а скорость очень высокая. (Вспомните HashMap в Java здесь).

Разница между индексом дерева B+ и индексом Hash

Если это эквивалентный запрос, хеш-индекс, очевидно, имеет абсолютное преимущество, потому что только один алгоритм может найти соответствующее значение ключа; конечно, предпосылка состоит в том, что значение ключа уникально, и в случае конфликта хэшей связанный список должен быть пройден.
Хэш-индекс не поддерживает запрос диапазона (но после преобразования LinkedHashMap в Java сохраняет порядок вставки узлов через связанный список, тогда вы также можете использовать связанный список для сохранения порядка размера данных)

Хотя этот метод поддерживает запрос диапазона, временная сложность составляет O(n), что менее эффективно, чем таблица пропуска и B+Tree.

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