В Об изучении InnoDB: путешествие в ядро, я представил проект innodb_diagrams для документирования внутренних компонентов InnoDB, который предоставляет диаграммы, используемые в этом посте. Позже в Кратком введении к innodb_ruby я прошел процедуру установки и несколько быстрых демонстраций инструмента командной строки innodb_space.
Физическая структура страниц INDEX InnoDB была описана в разделе Физическая структура страниц индекса InnoDB. Сейчас мы рассмотрим, как InnoDB логически структурирует свои индексы, используя некоторые практические примеры.
Отдельно от терминологии: B + Дерево, корень, лист и уровень
InnoDB использует структуру B + Tree для своих индексов. B + Tree особенно эффективен, когда данные не помещаются в память и должны быть прочитаны с диска, так как он гарантирует, что для доступа к любым запрошенным данным потребуется фиксированное максимальное количество чтений, основываясь только на глубине дерева , который хорошо масштабируется.
Дерево индекса начинается с «корневой» страницы, местоположение которой фиксировано (и постоянно хранится в словаре данных InnoDB) в качестве отправной точки для доступа к дереву. Дерево может иметь размер, равный одной корневой странице, или несколько миллионов страниц в многоуровневом дереве.
Страницы называются «листовыми» страницами или «не листовыми» страницами (в некоторых контекстах также называемыми «внутренними» или «узловыми» страницами). Листовые страницы содержат фактические данные строки. Неконечные страницы содержат только указатели на другие неконечные страницы или листовые страницы. Дерево сбалансировано, поэтому все ветви дерева имеют одинаковую глубину.
InnoDB назначает каждой странице в дереве «уровень»: листовым страницам назначается уровень 0, а приращения уровня идут вверх по дереву. Уровень корневой страницы зависит от глубины дерева. Все страницы, которые не являются ни листовыми, ни корневой страницей, также могут называться «внутренними» страницами, если различие важно.
Листовые и не листовые страницы
Как для конечных, так и для конечных страниц каждая запись (включая системные записи infimum и supremum) содержит указатель «следующая запись», в котором хранится смещение (внутри страницы) следующей записи. Связанный список начинается с минимума и связывает все записи в порядке возрастания по ключу, заканчиваясь на супремуме. Записи не упорядочены физически на странице (они занимают все свободное место на момент вставки); их единственный заказ происходит из их положения в связанном списке.
Листовые страницы содержат неключевые значения как часть «данных», содержащихся в каждой записи:
Неконечные страницы имеют идентичную структуру, но вместо неключевых полей их «данные» - это номер страницы дочерней страницы, и вместо точного ключа они представляют минимальный ключ на дочерней странице, которую они указать на:
Страницы на том же уровне
Большинство индексов содержат более одной страницы, поэтому несколько страниц связаны друг с другом в порядке возрастания и убывания:
Каждая страница содержит указатели (в заголовке FIL) для «предыдущей страницы» и «следующей страницы», которые для страниц INDEX используются для формирования двусвязного списка страниц на одном уровне (например, конечных страниц на уровне 0 формируют один список, страницы уровня 1 формируют отдельный список и т. Д.).
Подробный взгляд на одностраничный стол
Давайте рассмотрим большую часть того, что B + Tree связано на одной странице указателя:
Создать и заполнить таблицу
Тестовая таблица, используемая на рисунке выше, может быть создана и заполнена (убедитесь, что вы используете innodb_file_per_table и используете формат файла Barracuda):
CREATE TABLE t_btree (
i INT NOT NULL,
s CHAR(10) NOT NULL,
PRIMARY KEY(i)
) ENGINE=InnoDB;
INSERT INTO t_btree (i, s)
VALUES (0, "A"), (1, "B"), (2, "C");
Хотя эта таблица довольно маленькая и нереалистичная, она наглядно демонстрирует, как работают записи и обход записей.
Проверка базовой структуры файла пространства
Таблица должна соответствовать тому, что мы рассмотрели ранее, сстандартные стандартные служебные страницы (FSP_HDR, IBUF_BITMAP и INODE), за которыми следует одна страница INDEX для корня индекса, и в этом случае две неиспользуемые страницы ALLOCATED.
$ innodb_space -f t_btree.ibdspace-page-type-region
start end count type
0 0 1 FSP_HDR
1 1 1 IBUF_BITMAP
2 2 1 INODE
3 3 1 INDEX
4 5 2 FREE (ALLOCATED)
Режим space-index-pages-summary даст нам количество записей на каждой странице и покажет ожидаемые 3 записи:
$ innodb_space -f t_btree.ibd space-index-pages-summary
page index level data free records
3 18 0 96 16156 3
4 0 0 0 16384 0
5 0 0 0 16384 0
(Обратите внимание, что space-index-pages-summary также показывает пустые ALLOCATED страницы как пустыестраницы с нулевыми записями, так как это часто то, что вас интересует для построения графиков.)
Режим пробелов показывает статистику нашего индекса PRIMARY KEY, который потребляет одну страницу во внутреннем файле.сегмент:
$ innodb_space -f t_btree.ibd space-indexes
id root fseg used allocated fill_factor
18 3 internal 1 1 100.00%
18 3 leaf 0 0 0.00%
Настройка дескриптора записи Для того, чтобы innodb_ruby мог выполнить синтаксический анализсодержание записей, мы пнеобходимо предоставить описатель записи, который является просто классом Ruby, предоставляющим метод, который возвращает описание индекса:
класс SimpleTBTreeDescriber
Необходимо отметить, что это кластеризованный ключ, предоставить описания столбцов для ключа и описания столбцов для неключевого ключа («Ряд») полей.Необходимо попросить innodb_space загрузить этот класс со следующими дополнительными аргументами:
-r -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber
Посмотрите насодержимое записи Корневую страницу (которая является листовой страницей) в этом примере можно выгрузить, используя режим дампа страницы и предоставив номер страницы для корневой страницы:
$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d
SimpleTBTreeDescriber -p 3 page-dump
Помимо некоторых частей этого вывода, которые мы рассмотрели ранее, этотеперь будет печатать раздел «records:» со следующей структурой для каждой записи:
{:format=>:compact,
:offset=>125,
:header=>
{:next=>157,
:type=>:conventional,
:heap_number=>2,
:n_owned=>0,
:min_rec=>false,
:deleted=>false,
:field_nulls=>nil,
:field_lengths=>[0, 0, 0, 0],
:field_externs=>[false, false, false, false]},
:next=>157,
:type=>:clustered,
:key=>[{:name=>"i", :type=>"INT", :value=>0, :extern=>nil}],
:transaction_id=>"0000000f4745",
:roll_pointer=>
{:is_insert=>true, :rseg_id=>8, :undo_log=>{:page=>312, :offset=>272}},
:row=>[{:name=>"s", :type=>"CHAR(10)", :value=>"A", :extern=>nil}]}
Это должно полностью соответствовать приведенной выше подробной иллюстрации, поскольку я скопировал большую часть информации из этого примера для точности.Обратите внимание на следующие аспекты:
Формат: compact: указывает, что запись является новым «компактным» форматом в таблицах формата Barracuda (в отличие от «избыточного» в таблицах антилоп).Ключ: key, указанный в выходных данных, представляет собой массив полей ключа для индекса, а: row - массив неключевых полей.Поля :action_id и: roll_pointer являются внутренними полями для MVCC, включенными в каждую запись, поскольку это кластерный ключ (PRIMARY KEY).Поле: next в хэше: header является относительным смещением (32), которое необходимо добавить к текущему смещению записи (125), чтобы получить фактическое смещение следующей записи (157).Для удобства это вычисленное смещение включено как: следующее в хэш записи.Рекурсный индекс Хороший и простой вывод рекурсивного индекса целиком может быть достигнут с помощью режима индексного рекурса, но, поскольку это все еще одностраничный индекс, выходные данные будут очень короткими:
$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d
SimpleTBTreeDescriber -p 3 index-recurse
ROOT NODE #3: 3 records, 96 bytes
RECORD: (i=0) -> (s=A)
RECORD: (i=1) -> (s=B)
RECORD: (i=2) -> (s=C)
Создание нетривиального индексаtree Многоуровневое дерево индексов (чрезмерно упрощенное) в InnoDB выглядит следующим образом:
Как описано выше, все страницы на каждом уровнеДважды связаны друг с другом, и на каждой странице записи одиночно связаны в порядке возрастания.Не листовые страницы содержат «указатели» (содержащие номер дочерней страницы), а не неключевые данные строк.
Если мы используем более простую схему таблицы с 1 миллионом строк, созданных в Кратком введении в innodb_ruby, деревоструктура выглядит немного интереснее:
$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 3 index-recurse
ROOT NODE #3: 2 records, 26 bytes
NODE POINTER RECORD >= (i=252) -> #36
INTERNAL NODE #36: 1117 records, 14521 bytes
NODE POINTER RECORD >= (i=252) -> #4
LEAF NODE #4: 446 records, 9812 bytes
RECORD: (i=1) -> ()
RECORD: (i=2) -> ()
RECORD: (i=3) -> ()
RECORD: (i=4) -> ()
NODE POINTER RECORD >= (i=447) -> #1676
LEAF NODE #1676: 444 records, 9768 bytes
RECORD: (i=447) -> ()
RECORD: (i=448) -> ()
RECORD: (i=449) -> ()
RECORD: (i=450) -> ()
NODE POINTER RECORD >= (i=891) -> #771
LEAF NODE #771: 512 records, 11264 bytes
RECORD: (i=891) -> ()
RECORD: (i=892) -> ()
RECORD: (i=893) -> ()
RECORD: (i=894) -> ()
Этотрехуровневое дерево индексов, которое видно по строкам ROOT, INTERNAL, LEAF выше.Мы можем видеть, что некоторые страницы полностью заполнены: 468 записей потребляют почти 15 КБ на странице 16 КБ.
Просмотр страницы без листа (страница 36, в приведенном выше выводе) с использованием дамп страницыВ этом режиме записи выглядят немного иначе, чем листовые страницы, показанные ранее:
$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 36 page-dump
{:format=>:compact,
:offset=>125,
:header=>
{:next=>11877,
:type=>:node_pointer,
:heap_number=>2,
:n_owned=>0,
:min_rec=>true,
:deleted=>false,
:field_nulls=>nil,
:field_lengths=>[0],
:field_externs=>[false]},
:next=>11877,
:type=>:clustered,
:key=>[{:name=>"i", :type=>"INT UNSIGNED", :value=>252, :extern=>nil}],
:child_page_number=>4}
Массив: key присутствует, хотя он представляет минимальный ключ, а не точный ключ, и no: row присутствует, так как вместо него: child_page_number.
Корневая страница немного особенная Поскольку корневая страница выделяется при первом создании индекса, и этот номер страницы сохраняется в словаре данных, корневая страница никогда не может быть перемещена или удалена.Как только корневая страница заполняется, ее необходимо разделить, образуя небольшое дерево корневой страницы плюс две конечные страницы.
Однако сама корневая страница фактически не может быть разделена, поскольку ее нельзяпереселены.Вместо этого выделяется новая пустая страница, туда перемещаются записи в корне (корень «поднимается» на уровень), и эта новая страница разбивается на две части.Тогда корневая страница не должна быть разделена снова, пока уровень непосредственно под ней не будет иметь достаточного количества страниц, чтобы корень заполнялся указателями дочерних страниц (так называемыми «указателями узлов»), что на практике часто означает от нескольких сотен до более тысячи.
B + Уровни дерева и увеличение глубины дерева В качестве примера эффективности индексов B + Tree предположим, что идеально упакована запись (каждая страница заполнена, что на практике никогда не случится, нополезно для обсуждения).Индекс B + Tree в InnoDB для простой таблицы в приведенных выше примерах сможет хранить 468 записей на листовой странице или 1203 записи на листе без листьев.В этом случае дерево индекса может иметь максимум следующих размеров при данных высотах дерева:
Height Non-leaf pages Leaf pages Rows Size in bytes
1 0 1 468 16.0 KiB
2 1 1203 > 563 thousand 18.8 MiB
3 1204 1447209 > 677 million 22.1 GiB
4 1448413 1740992427 > 814 billion 25.9 TiB
Как вы можете себе представить, большинство таблиц с разумными определениями PRIMARY KEY имеют 2-3 уровня, а некоторые достигают 4 уровней,Однако использование чрезмерно большого PRIMARY KEY может привести к тому, что B + Tree будет гораздо менее эффективным, поскольку значения первичного ключа должны храниться на страницах без листа.Это может значительно увеличить размер записей на неконечных страницах, а это означает, что гораздо меньше таких записей помещается на каждой неконечной странице, что делает всю структуру менее эффективной.