В статье визуализируется структура индекса и показывается, как меняется структура индекса типа btree в PostgreSQL. Это полезно для понимания, как выглядят индексы btree. Также рассматривается FILLFACTOR и пример исследования структуры индекса в целях определения, как перераспределяются индексные записи при включении в структуру индекса новых блоков (страниц).

Создадим простую таблицу, индекс, вставим три строки:

create table t(s text storage plain) with (autovacuum_enabled=off, fillfactor=10);
create index t_idx on t (s) with (fillfactor=10, deduplicate_items = off);
insert into t values (repeat('a',2500));
insert into t values (repeat('b',2500));
insert into t values (repeat('c',2500));

Размер полей выбран так, чтобы в блок таблицы помещалась одна строка, а в блок индекса индекса помещались 3-4 строки.

В расширении pageinspect есть функции для просмотра структуры блоков индексов. Функции для индексов типа btree имеют префикс bt_ . Адрес корневого блока «дерева» (логической структуры) индекса и число уровней индекса можно посмотреть запросом:

create extension if not exists pageinspect;
select * from bt_metap('t_idx');
magic  | version | root | level | fastroot | fastlevel |last_cleanup_|last_cleanup|allequalimage
       |         |      |       |          |           |num_delpages | _num_tuples|
-------+---------+------+-------+----------+-----------+-------------+------------+-------------
340322 |       4 |    1 |     0 |        1 |         0 |           0 |         -1 | t

Число уровней индекса показывает level. Нумерация начинается с нуля. Дерево индекса растёт снизу вверх и ноль соотвествует листовым блокам.

Поля magic и version используются для быстрой проверки того, что объект является индексом btree поддерживаемой версии. "Магическое" число для индексов типа btree равно 340322 (0x0531162).

Версия индекса показана в столбце version=4. Начиная с PostgreSQL версии 12 используется 4 версия индексов. Более старая версия индекса может встретиться, если СУБД обновлялась со старых версий. Индексы старых версий работают, но новшества не поддерживают. Индексы старых версий достаточно перестроить, версия обновится, новшества начнут использоваться.

Адрес корневого блока индекса хранится в root. Число в root - это порядковый номер блока с начала первого файла данных индекса. fastroot и fastlevel используются для несущественной оптимизации поиска по индексу (это не оптимизация вставки в правый листовой блок, которая существенна, но эти две оптимизации часто путают). В примере fastroot тот же, что и root. Пример изменения значения fastroot будет приведён позже, после удаления всех строк.

Данные по всем блокам индекса можно посмотреть запросом:

select blkno, type, live_items live, avg_item_size size,
free_size free, btpo_prev prev,  btpo_next next, btpo_level level,
btpo_flags fl from bt_multi_page_stats('t_idx',1,-1);
 blkno | type | live | size | free | prev | next | level | fl 
-------+------+------+------+------+------+------+-------+----
     1 | l    |    3 | 2512 |  600 |    0 |    0 |     0 |  3

В дереве (логической структуре) индекса пока один блок,поэтому выдана одна строка. Дальше будем вставлять строки и смотреть этим запросом структуру блоков индекса.

Содержимое блока индекса можно посмотреть запросом:

select itemoffset o, ctid, itemlen, htid, left(data::text,18) data,
chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c
from bt_page_items('t_idx',1);
 o | ctid  | itemlen | htid  |        data        | c 
---+-------+---------+-------+--------------------+---
 1 | (0,1) |    2512 | (0,1) | 20 27 00 00 61 61  | a
 2 | (1,1) |    2512 | (1,1) | 20 27 00 00 62 62  | b
 3 | (2,1) |    2512 | (2,1) | 20 27 00 00 63 63  | c
(3 rows)

ctid хранит адрес строки в таблице, на которую указывает индексная запись в формате (блок, сторка в блоке). В примере каждая строка таблицы находится в своём блоке. data хранит проиндексировангое значение. На основе этих запросов уже можно нарисовать структуру индекса:

структура индекса для 3 проиндексированных строк

Физически, в индексе два блока: нулевой блок всегда содержит метаданные; блок номер 1 содержит три записи. Для компактности поиндексированные значения полей таблицы отображены одной буквой, а не 2500 буквами. Буква a в шестнадцатеричном виде 61, буква b - 62, буква c - 63.

Дальше, вставляя по одной строке, будут выполнены запросы и на основе запросов нарисована структура индекса. Можно просматривать результаты запросов и сопоставлять их с рисунком. Это полезно, чтобы понять, как растёт индекс btree в PostgreSQL.

После вставки четвёртой строки

После вставки четвёртой строки можно выполнить следующие запросы и на основе их результатов нарисовать структуру индекса:

insert into t values (repeat('d',2500));
select ctid, left(s, 24) from t;
select blkno, type, live_items live, avg_item_size size, free_size free, btpo_prev prev,  btpo_next next, btpo_level level, btpo_flags fl from bt_multi_page_stats('t_idx',1,-1);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',1);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',2);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',3);
INSERT 0 1
 ctid  |           left           
-------+--------------------------
 (0,1) | aaaaaaaaaaaaaaaaaaaaaaaa
 (1,1) | bbbbbbbbbbbbbbbbbbbbbbbb
 (2,1) | cccccccccccccccccccccccc
 (3,1) | dddddddddddddddddddddddd
(4 rows)

 blkno | type | live | size | free | prev | next | level | fl 
-------+------+------+------+------+------+------+-------+----
     1 | l    |    2 | 2512 | 3116 |    0 |    2 |     0 |  1
     2 | l    |    3 | 2512 |  600 |    1 |    0 |     0 |  1
     3 | r    |    2 | 1260 | 5620 |    0 |    0 |     1 |  2
(3 rows)

 o | ctid  | itemlen | htid  |        data        | c 
---+-------+---------+-------+--------------------+---
 1 | (1,1) |    2512 |       | 20 27 00 00 62 62  | b
 2 | (0,1) |    2512 | (0,1) | 20 27 00 00 61 61  | a
(2 rows)

 o | ctid  | itemlen | htid  |        data        | c 
---+-------+---------+-------+--------------------+---
 1 | (1,1) |    2512 | (1,1) | 20 27 00 00 62 62  | b
 2 | (2,1) |    2512 | (2,1) | 20 27 00 00 63 63  | c
 3 | (3,1) |    2512 | (3,1) | 20 27 00 00 64 64  | d
(3 rows)

 o | ctid  | itemlen | htid |        data        | c 
---+-------+---------+------+--------------------+---
 1 | (1,0) |       8 |      |                    | 
 2 | (2,1) |    2512 |      | 20 27 00 00 62 62  | b
(2 rows)

Корневым стал 3 блок. При дальнейших вставках корневой блок будет также меняться.

Первая строка в промежуточных и листовых блоках кроме самых "правых" всегда хранит служебное значение, называемое "High key" (выделена красным цветом). После вставки 4 строки в структуре индекса впервые появился "не правый" листовой блок. High key хранит значение, большее, чем те, которые могут встретиться в этом блоке. Об этой служебной записи будет ещё упомянуто после вставки 7 строки.

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

Почему другой процесс мог расщепить блок? Потому, что структура индексов btree оптимизирована для конкурентных чтений и изменений блоков индекса. С индексными блоками одновременно и не блокируя друг друга могут работать несколько процессов. Структура индекса и алгоритмы работы с индексом обеспечивают непротиворечивость. Нельзя сказать, что блокировок совсем нет. Блокировки устанавливаются на доступ к буферу, в котором находится блок индекса. Буфера блокируются каждым процессом по одному, а не по несколько. Пока процесс спускается с блока вышестоящего уровня, блок нижестоящего уровня может измениться.

В блоке синего цвета есть High Key? Нет, так как это корневой блок и на своём «корневом» уровне он считается «правым» блоком. В правых блоках High Key нет. HighKey не хранится в самых правых блоках каждого уровня, так как нет смысла обозначать правую границу - блок и так самый правый, а HighKey используется для проверки того не нужно ли считывать блок правее.
Поле data текущей и следующей (itemoffset+1) записи задаёт диапазон, в который должно попасть значение, по которому выполняется поиск в индексе.

Что находится в первой записи этого корневого блока и почему там в поле data пустое значение? Первая строка itemoffset=1 , ctid=(1,0) указывает на блок нижнего уровня, который будет самым левым на своём уровне и в поле data хранит пустое значение, которое трактуется, как «минус бесконечность». На отстутствие значения в поле data указывает ноль в ctid=(1,0). На присутствие указывает единица вместо ноля.

После вставки 5 строк

insert into t values (repeat('e',2500));
select ctid, left(s, 24) from t;
select blkno, type, live_items live, avg_item_size size, free_size free, btpo_prev prev,  btpo_next next, btpo_level level, btpo_flags fl from bt_multi_page_stats('t_idx',1,-1);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',1);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',2);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',3);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',4);

После вставки 6 строки

insert into t values (repeat('f',2500));

Скрытый текст

select ctid, left(s, 24) from t;
select blkno, type, live_items live, avg_item_size size, free_size free, btpo_prev prev, btpo_next next, btpo_level level, btpo_flags fl from bt_multi_page_stats('t_idx',1,-1);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',1);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',2);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',3);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',4);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',5);
INSERT 0 1
ctid | left
-------+--------------------------
(0,1) | aaaaaaaaaaaaaaaaaaaaaaaa
(1,1) | bbbbbbbbbbbbbbbbbbbbbbbb
(2,1) | cccccccccccccccccccccccc
(3,1) | dddddddddddddddddddddddd
(4,1) | eeeeeeeeeeeeeeeeeeeeeeee
(5,1) | ffffffffffffffffffffffff
(6 rows)

blkno | type | live | size | free | prev | next | level | fl
-------+------+------+------+------+------+------+-------+----
     1 | l    |    2 | 2512 | 3116 |    0 |    2 |     0 | 1
     2 | l    |    2 | 2512 | 3116 |    1 |    4 |     0 | 1
     3 | r    |    4 | 1886 | 588 |    0 |    0 |     1 | 2
     4 | l    |    2 | 2512 | 3116 |    2 |    5 |     0 | 1
     5 | l    |    3 | 2512 | 600 |    4 |    0 |     0 | 1
(5 rows)
o | ctid | itemlen | htid |        data        | c
---+-------+---------+-------+--------------------+---
1 | (1,1) |    2512 |       | 20 27 00 00 62 62 | b
2 | (0,1) |    2512 | (0,1) | 20 27 00 00 61 61 | a
(2 rows)

o | ctid | itemlen | htid |        data        | c
---+-------+---------+-------+--------------------+---
1 | (2,1) |    2512 |       | 20 27 00 00 63 63 | c
2 | (1,1) |    2512 | (1,1) | 20 27 00 00 62 62 | b
(2 rows)

o | ctid | itemlen | htid |        data        | c
---+-------+---------+------+--------------------+---
1 | (1,0) |       8 |      |                    |
2 | (2,1) |    2512 |      | 20 27 00 00 62 62 | b
3 | (4,1) |    2512 |     | 20 27 00 00 63 63 | c
4 | (5,1) |    2512 |      | 20 27 00 00 64 64 | d
(4 rows)

o | ctid | itemlen | htid |        data        | c
---+-------+---------+-------+--------------------+---
1 | (3,1) |    2512 |       | 20 27 00 00 64 64 | d
2 | (2,1) |    2512 | (2,1) | 20 27 00 00 63 63 | c
(2 rows)

o | ctid | itemlen | htid |        data        | c
---+-------+---------+-------+--------------------+---
1 | (3,1) |    2512 | (3,1) | 20 27 00 00 64 64 | d
2 | (4,1) |    2512 | (4,1) | 20 27 00 00 65 65 | e
3 | (5,1) |    2512 | (5,1) | 20 27 00 00 66 66 | f
(3 rows)

После вставки 7 строки

insert into t values (repeat('g',2500));
select blkno, type, live_items live, avg_item_size size, free_size free, btpo_prev prev,  btpo_next next, btpo_level level, btpo_flags fl from bt_multi_page_stats('t_idx',1,-1);
 blkno | type | live | size | free | prev | next | level | fl 
-------+------+------+------+------+------+------+-------+----
     1 | l    |    2 | 2512 | 3116 |    0 |    2 |     0 |  1
     2 | l    |    2 | 2512 | 3116 |    1 |    4 |     0 |  1
     3 | i    |    3 | 1677 | 3104 |    0 |    7 |     1 |  0
     4 | l    |    2 | 2512 | 3116 |    2 |    5 |     0 |  1
     5 | l    |    2 | 2512 | 3116 |    4 |    6 |     0 |  1
     6 | l    |    3 | 2512 |  600 |    5 |    0 |     0 |  1
     7 | i    |    3 | 1677 | 3104 |    3 |    0 |     1 |  0
     8 | r    |    2 | 1260 | 5620 |    0 |    0 |     2 |  2
(8 rows)

В индекс будет добавлено сразу три блока, так как увеличится число уровней индекса и на двух уровнях блоки разделятся:

для 7 строк во внутреннем блоке номер 3 появился HighKey

Корневым стал 8 блок вместо 3. Добавление нового уровня привело к особенности в 3 блоке: в этом блоке появилась запись, хранящая так называемый HighKey (высокий ключ). Он впервые встретился в блоке промежуточного уровня. Вторую запись в 3 блоке "логичнее" было бы сделать первой. Однако, она идёт второй и это не является ошибкой. Также на 4 блок есть два указателя из двух блоков вышестоящего уровня. Это также не является ошибкой. Красная стрелка указывает на значение, которое будет сравниваться. При навигации с 3 на 2 блок значение ctid=(4,1) может поменяться. Значение ctid=(4,1) актуально только в момент создания записи. Навигация по нему (по High Key) не выполняется, поэтому черная стрелка (по которым ходит процесс) не рисуется. Навигации вверх (возврат на тот блок, с которого процесс спустился на текущий) нет, так как за время спуска вниз исходный блок может успеть расщепиться и поменяться. Поэтому навигация по черным стрелкам в одном направлении. Если нужно вернуться на уровень вверх, то начинать нужно с корневого блока.

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

Первая строка (itemoffset=1) в блоках кроме самых "правых" всегда хранит служебное значение, называемое "High key". Корневой является "правым". При вставке в структуру индекса нового блока обновляются High keys и ссылки на соседние блоки того же уровня. High key хранит значение, большее, чем те, которые могут встретиться в этом блоке.

Второй момент. Вторая запись в корневом (синего цвета) блоке ctid=(7,1) data=«c» может удивить, так как в правом промежуточном блоке номер 7 (зеленого цвета) значения “c” нет. В первой записи 7 блока data пусто (минус бесконечность), но если спуститься по этой ссылке ctid=(4,0), то попадаем в листовой блок индекса номер 4, где хранится ссылка на сроку таблицы со значением “c”. В ctid, которые ведут на блоки индекса, второе число либо 0, либо 1 и это не номер записи,а обозначение, что data пуста (минус бесконечность) или хранит минимальное значение, которое присутствует в дочернем листовом блоке.

После вставки 8 строки

insert into t values (repeat('h',2500));

9 строк достаточно, чтобы проследить рост структуры индекса:

Как изменится структура индекса после перестроения

reindex index t_idx;

после перестройки (REINDEX) индекса по 9 строкам

Число блоков индекса увеличислось до 12. Визуально, структура индекса существенно не изменилась. До перестройки индекс был оптимален. Можно сделать вывод, что вставка строк с возрастающими значениями, оставляет структуру индекса btree в PostgreSQL оптимальной.

Структура индекса после удаления строк

После удаления всех строк в таблице в индексе число уровней не меняется, а fasroot укажет на листовой блок:

delete from t;
select root, level, fastroot, fastlevel, 
last_cleanup_num_delpages, allequalimage from bt_metap('t_idx');
vacuum t;
select version, root, level, fastroot, fastlevel, 
last_cleanup_num_delpages delpages, 
last_cleanup_num_tuples tuples, allequalimage from bt_metap('t_idx');
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',9);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',10);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',11);
select itemoffset o, ctid, itemlen, htid, left(data::text,18) data, chr(nullif(('0x0'||substring(data from 13 for 2))::integer,0)) c from bt_page_items('t_idx',12);

После удаления всех строк fastroot не менялся и блоки не были исключены их структуры индекса.

После вакуумирования девять блоков (в примере приведён запрос по 10 блоку) было исключено из структуры индекса, осталось 3 (отмечены зеленым цветом) правых блока на каждом уровне. fastroot стал указывать на листовой блок 11. С этого блока теперь будет начинаться поиск с помощью этого индекса. На чио это влияет? При поиске по индексу не будут читаться два блока: 9 и 12. В этом и состоит оптимизация fastroot.

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

структура индекса после удаления всех строк

В файле индекса осталось 12 блоков. Размер файла основного слоя (main fork) индекса не уменьшился.

Чтение структуры индекса

Мы рассмотрели структуру простого индекса. Посмотрим пример чтения структуры более сложного индекса. Создадим индекс по численному столбцу таблицы с миллионом строк, что ближе к реально используемым индексам.

create table t3 (id bigserial primary key, s int4) with (autovacuum_enabled=off);
insert into t3 (s) select * from generate_series(1, 1000000);
select * from bt_metap('t3_pkey');
 magic  | version | root | level | fastroot | fastlevel |last_cleanup_|last_cleanup|allequalimage
        |         |      |       |          |           |num_delpages | _num_tuples|
--------+---------+------+-------+----------+-----------+-------------+------------+-------------
 340322 |       4 |  412 |     2 |      412 |         2 |           0 |         -1 | t

В результатах функции интерес представляют только level и root.

Число уровней level=2. Нумерация начинается с нуля. Дерево индекса растёт снизу вверх и нуль соответствует листовым блокам.

Корневой блок индекса root=412. Число - порядковый номер блока с начала первого файла слоя данных индекса.

Функция bt_page_stats и спользуется для навигации по структуре индекса и выдаёт одну строку для каждого блока индекса. Данные по корневому блоку индекса t3_pkey:

select * from bt_page_stats('t3_pkey',412);
blkno|type|live_items|dead_items|avg_item_size|free_size| btpo_prev | btpo_next | btpo_level | btpo_flags 
-----+----+----------+----------+-------------+---------+-----------+-----------+------------+-----------
 412 | r  |        9 |        0 |          15 |    7976 |         0 |         0 |          2 |        2

Для навигации используются поля btpo_prev и btpo_next. В этих полях указаны номера блоков левее и правее на том же уровне. btpo_prev=0 означает, что блок самый левый, btpo_next=0 означает, что блок самый правый на своём уровне. Корневой блок единственный на своём уровне, поэтому значения нули.

Тип блока указан в поле type. Значения в этом столбце: r - корневой (root); i - внутренний (internal); l - листовой (list), e - (ignored), d - удалёный листовой (deleted leaf), D - удалённый внутренний (deleted internal).

avg_item_size показывает вычисленное значение среднего размера индексной записи в этом блоке. Записи выравниваются по 8 байт.

live_items - сколько записей есть в этом блоке.

Для просмотра индексных записей используется функция bt_page_items. Индексные записи в корневом блоке индекса t3_pkey:

описание результатов функции bt_page_items

В индексе используются оптимизация suffix truncation и усечение проиндексированных столбцов в поле data её следствие. Из-за этой оптимизации индекс btree используемый в PostgreSQL можно называть "Simple Prefix B-Tree". Простое (Simple) потому, что усекаются целые поля (whole "attribute" truncation). Для индекса по одному столбцу остаётся пустота, трактуемая как минус бесконечность.

Длина первой записи за счёт отсутствия значения в поле data 8 байт: itemlen=8.

Что выдаёт функция bt_page_stats по блоку с itemoffset=1:

select blkno, type, live_items live, dead_items dead, avg_item_size size, free_size free, btpo_prev, btpo_next, btpo_level l, btpo_flags f from bt_page_stats('t3_pkey', 3);
 blkno | type | live | dead | size | free | btpo_prev | btpo_next | l | f 
-------+------+------+------+------+------+-----------+-----------+---+---
     3 | i    |  286 |    0 |   15 | 2436 |         0 |       411 | 1 | 0

3 блок самый левый на своём уровне, на это указывает btpo_prev=0.

В 3 блоке 286 записей. Блок наполнен на 70%, что является значением процента заполнения по умолчанию для промежуточных блоков.

Что выдаёт функция bt_page_stats по блоку с itemoffset=9:

select blkno, type, live_items live, dead_items dead, avg_item_size size, free_size free, btpo_prev, btpo_next, btpo_level l, btpo_flags f from bt_page_stats('t3_pkey', 2414);
 blkno | type | live | dead | size | free | btpo_prev | btpo_next | l | f 
-------+------+------+------+------+------+-----------+-----------+---+---
  2414 | i    |  184 |    0 |   15 | 4476 |      2128 |         0 | 1 | 0

2414 блок самый правый на своём уровне, на это указывает btpo_next=0.

В 2414 блоке 184 записи. Это самый правый блок своего уровня, он заполнен не на 70%, а меньше. Это произошло из-за того, что при заполнении монотонно возрастающей последовательностью, вставки выполняются в правый листовой блок и именно он делится. Вставка записи со ссылкой на новый листовой блок выполняется в самый правый блок вышестоящего уровня. Делятся самые правые блоки каждого уровня. После деления записи перераспределяются между двумя блоками. В блоке "левее" остаётся 70% записей для промежуточных блоков. При делении листового блока, в блоке "левее" остаётся fillfactor записей. Оставшиеся записи, как у промежуточного, так и у листового блока остаются в "правом" блоке и их меньше, чем в блоке "левее" от него. Именно поэтому в "правом" 2414 блоке 184 записи, что меньше, чем 286.

Что выдаёт функция bt_page_stats по блоку с itemoffset=2:

select blkno, type, live_items live, dead_items dead, avg_item_size size, free_size free, btpo_prev, btpo_next, btpo_level l, btpo_flags f from bt_page_stats('t3_pkey', 411);
 blkno | type | live | dead | size | free | btpo_prev | btpo_next | l | f 
-------+------+------+------+------+------+-----------+-----------+---+---
   411 | i    |  286 |    0 |   15 | 2436 |         3 |       698 | 1 | 0

411 блок стоит справа от блока 3, на это указывает btpo_prev=3.

Значения btpo_prev и btpo_next соответствуют порядку следования записей столбца itemoffset. вышестоящего блока. В примере btpo_next=698, что соответствует записи с itemoffset=3 в вышестоящем блоке.

Во всех промежуточных блоках, кроме "правых" число записей (286) и свободное место (free) соответствует 70% заполнению потому, что вставки были в правые блоки. В результате деления правых блоков (когда в них не оставалось места для вставки) левые блоки заполнялись на 70% (промежуточные, внутренние) или до fillfactor (листовые).

FILLFACTOR в индексах типа btree

Если при вставке строки в таблицу делится самая правая страница на уровне (последняя страница уровня), то деления поровну не происходит, левая страница заполняется до fillfactor, а правая остается почти свободной. Это полезно для индексов на автоинкрементальные столбцы или заполняемые возрастающей последовательностью, так как вставки будут всегда идти в самый правый листовой блок и он будет делиться. Для таких индексов стоит устанавливать fillfactor=100, иначе индексы будут иметь больший размер, место в листовых блоках будет расходоваться впустую. В случае установки fillfactor=100 левый блок при делении самого правого листового блока будет максимально заполнен, данные будут храниться более компактно, деление правого блока будет происходить реже. Промежуточные блоки таких индексов будут заполняться на 70% независимо от значения fillfactor. Однако промежуточные блоки вносят небольшой вклад в размер индекса. Для числового столбца (int2, int4, int8) в промежуточном блоке при 70% заполнения помещается 286 ссылок, при 100% поместится 407 ссылок.

В индексах типа btree fillfactor установлен в значения:
1) 90% для листовых блоков (BTREE_DEFAULT_FILLFACTOR=90)
2) 70% для нелистовых блоков и это не меняется (BTREE_NONLEAF_FILLFACTOR=70).

Для листовых блоков fillfactor применяется:
1) во время построения индекса
2) при разделении крайней правой страницы как листового, так и промежуточных уровней.

При разделении не самых правых страниц данные перераспределяются поровну. В родительский блок вставляется ссылка на второй блок. Если в родительском блоке нет места, то он делится и так до корневого блока. Если в корневом блоке нет места, то добавляется новый уровень. При разделении любого (в том числе правого) листового блока, который полностью заполнен одним и тем же значением (дубликатами) fillfactor=96 (BTREE_SINGLEVAL_FILLFACTOR=96).

Заключение

По данным функций расширения pageinspect визуализирована структура индекса и показаны примеры, как читать структуру индекса типа btee PostgreSQL. Показан пример исследования структуры индекса, чтобы проверить какое значение FILLFACTOR используется для внутренних блоков индекса btree. В статье не рассматривались примеры дедуплицирования индексных записей, составные индексы и индексы с неключевыми столбцами (include).

Визуальное представление структуры btree индекса PostgreSQL