Сколько данных может хранить дерево B+ высотой 3?

1. Предпосылки

Когда студенты участвовали в интервью Али, их спросили, сколько данных может хранить индекс дерева B+. Этот вопрос очень интересен.Если вы мало знаете о деревьях B+, то, вероятно, на этот вопрос будет нелегко ответить.

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

Создать новую таблицу

CREATE TABLE IF NOT EXISTS `person`(
   `id` INT UNSIGNED AUTO_INCREMENT,
   `name` VARCHAR(64) NOT NULL,
   PRIMARY KEY ( `id` )
)ENGINE=InnoDB DEFAULT CHARSET=utf8;

2. Структура страницы InnoDB

В InnoDB структура данных, используемая индексом, по умолчанию представляет собой дерево B+, иB+树里的每个节点都是一个页, размер страницы по умолчанию16KB.
Неконечные узлы хранят значения индекса и смещения страниц, а конечные узлы хранят полные записи каждой строки.

Если вы примерно знаете, что хранится на странице и сколько места она занимает, вы можете оценить, сколько фрагментов данных может быть сохранено.

Сосредоточьтесь на зеленой части здесь. Я особо не нарисовал, а что такое File Header, Page Header и т. д., я не буду вдаваться в подробности ни для какого использования.Если вам интересно, вы можете сами перейти к 4.4 «MySQL Technology Insider», перейти к моему анализу этого.IBD файл таблицы лиц, как написать гаджет, который проверяется ниже

Ссылки на гаджеты:GitHub.com/52123/в кивок…

3. Сколько данных может хранить дерево B+?

3.1 Сколько данных может хранить нелистовой узел

Страница по умолчанию 16 КБ
Заголовок файла, заголовок страницы и т. д. занимают всего 102 байта.
Infimum + Supremum занимают по 13 байт
Заголовок записи занимает 5 байт
id занимает int, занимая 4 байта
Смещение каталога страниц занимает 4 байта

Итак, сколько записей индекса может хранить нелистовой узел?

   非叶子节点能存放的索引记录
=  (页大小 - File Header - Page Header - ...) / ( 主键 + 页偏移量 + 下一条记录的偏移量)
= （16KB - 128B) / (5B + 4B + 4B) 
=  16256 / 13
=  1250 条

3.2 Сколько данных может хранить конечный узел

Сколько записей данных может хранить конечный узел?

Список переменной длины занимает 1 байт
Нулевой флаг игнорируется
Заголовок записи занимает 5 байт
id занимает int, занимая 4 байта
Имя VARCHAR и кодировка UTF8.Для расчета я использую только два китайских символа для всех строковых записей, то есть 2 * 3B = 6 байт
Столбец идентификатора транзакции занимает 6 байт.
Столбец указателя отката занимает 7 байт.

   叶子节点能存放的数据记录
=  (页大小 - File Header - Page Header - ...) / ( 主键 + 字段 + 下一条记录的偏移量)
= （16KB - 128B) / (1B + 5B + 4B + 6B + 6B + 7B) 
=  16256 / 29
=  560 条

3.3 Сколько строк записей данных может хранить дерево B+ высотой 3

Корневой узел может содержать 1250 записей индекса.
Второй уровень может содержать 1250 * 1250 = 1 562 500 записей индекса.
Конечный узел 1250 * 1250 * 560 = 875 000 000 записей данных, более 800 миллионов данных

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

4. Подтвердите это

Написал скрипт для генерации SQL для пакетной вставки, вставив 27 090 000 фрагментов данных.

В соответствии с размером и значением Заголовка файла, Заголовка страницы, Infimum, Supremum и Заголовка записи я написал небольшой инструмент на Python, чтобы помочь проверить, соответствует ли объем данных, хранящихся на каждой странице, тому, что я предположил выше.

Полученные данные: высота дерева B+ равна 3, нелистовых узлов 46, листовых узлов 52501, количество записей индекса 52546, количество записей данных строки 27090000.

4.1 Сколько данных на самом деле может храниться в нелистовых узлах

   实际得到的非叶子节点能存放的索引记录
=  索引记录的数量 / 非叶子节点数量
=  52546 / 46
=  1142

Значение, рассчитанное в моем предположении (1250), очень близко, а почему фактический результат меньше, чем предположение?

Во-первых, я не считал каталог страниц, но распечатал количество слотов.Вы можете видеть, что для нелистовых узлов имеется 13150 слотов.Среднее количество слотов на странице 13150/46 = 286. Один слот занимает два байта, значит должно быть (16256 - 286 * 2) / 13 = 1206
Во-вторых, на самом деле не каждый нелистовой узел заполнен данными индекса, поэтому я считаю нормальным иметь десятки записей.

4.2 Сколько данных на самом деле может храниться в листовых узлах

   实际得到的叶子节点能存放的索引记录
=  行数据记录的数量 / 叶子节点数量
=  27090000 / 52546
=  516

Ну и рассчитанное по моим предположениям (560) тоже очень близко, и чуть хуже.

Считая слоты конечных узлов, средний слот каждого листового узла составляет 6825001/52501 = 130, тогда более точное предположение должно быть (16256 - 130 * 2)/29 = 551.
Как и выше, не каждый листовой узел точно заполнен.

4.3 Интересные моменты

Данные, которые мы только что получили

Есть 46 нелистовых узлов и 52501 листовой узел.
Количество записей индекса — 52546, а количество записей данных строки — 27090000.

На самом деле это索引记录的数量а также叶子节点的数量Это может быть сопоставлено, я посмотрел на корневой узел, он имеет 45 индексных записей, то есть

- 根节点，存了45条索引记录
- 第二层，存了52546 - 45 = 52501条索引记录数据
- 第三层，叶子节点，有52501个
这个第二层跟第三层刚好就是一条索引记录对应一个叶子节点

5. Делайте выводы о других вещах

Почему InnoDB по умолчанию использует дерево B+ в качестве структуры данных индекса

Важно: уменьшить дисковый ввод-вывод

InnoDB использует неконечные узлы дерева B+ для хранения значений первичного ключа и каталогов страниц, чтобы на странице можно было хранить больше записей индекса. Листовые узлы используются для хранения реальных записей строк, преимущество которых заключается в уменьшении высоты дерева и уменьшении дискового ввода-вывода. Объединив вышеизложенное, более 800 миллионов данных можно сохранить в виде дерева B+ высотой 3, и для получения желаемых данных из 800 миллионов данных требуется не более 3 дисковых операций ввода-вывода.

Почему бы не использовать B-дерево в качестве индексированной структуры данных?

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

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

6. Резюме

Структура данных индекса по умолчанию, используемая механизмом хранения InnoDB, является деревом B +, в то время какB+树里的每个节点都是一个页, размер страницы по умолчанию16KB

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

Заголовок файла занимает 38 байт
Заголовок страницы занимает 56 байт
Infimum и Supremum занимают по 13 байт.
Трейлер файла занимает 8 байт
Каждый слот в каталоге страниц занимает 2 байта.
Заголовок каждой записи занимает 5 байт (будь то запись индекса или запись данных строки имеет заголовок данных)

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

Одна из основных причин, по которой InnoDB использует деревья B+ в качестве структуры данных индекса по умолчанию, заключается в том, что减少磁盘的IO次数

Ссылаться на

Официальная документация MySQL - Механизм хранения InnoDB
"Инсайдер технологии MySQL (InnoDB Storage Engine), 2-е издание"
«Высокопроизводительный MySQL»