kb/indexes ── Индексы ── intermediate

B-tree: структура и спуск

B-tree - сбалансированное дерево из 8-КБ страниц: meta page указывает на корень, внутренние страницы хранят разделители и downlink, листья - ключ и ctid. Большой fanout даёт 3-4 уровня на миллиарды строк.

view as markdownaka: btree, btree-descent

B-tree - индекс по умолчанию, поддерживает <, <=, =, >=, >, BETWEEN, IN, IS NULL и выдаёт данные отсортированными.

Три роли страниц

meta page (страница 0) - указатель на корень и высоту дерева;
внутренние страницы - разделители и downlink на детей;
листовые страницы - ключ и ссылка ctid на строку.

Поиск: meta → корень → внутренние → лист. Увидеть руками через pageinspect:

sql

SELECT root, level FROM bt_metap('tickets_pkey');

SELECT itemoffset, ctid, data FROM bt_page_items('tickets_pkey', 1);

Почему дерево мелкое

На внутренней странице помещаются сотни разделителей, значит fanout - сотни детей. Глубина ≈ log_fanout(число строк): 3 уровня на десятки миллионов, 4 на миллиарды. Поэтому поиск по индексу - 3-4 чтения страниц, и индексный доступ дёшев при малой селективности (см. selectivity-crossover).

Сбалансированность

Все листья на одной глубине, путь от корня до любого листа одинаков - время поиска предсказуемо. Механизмы split, дедупликации и INCLUDE - в btree-internals. Тип индекса под оператор выбирают через operator-classes.

§ команды

bash

SELECT root, level FROM bt_metap('idx_name');

Корень и высота B-tree

bash

SELECT * FROM bt_page_items('idx_name', 1);

Содержимое страницы индекса (спуск по дереву)

§ см. также

kb/indexes ── Индексы ── intermediate

B-tree: структура и спуск

view as markdownaka: btree, btree-descent

B-tree - индекс по умолчанию, поддерживает <, <=, =, >=, >, BETWEEN, IN, IS NULL и выдаёт данные отсортированными.

Три роли страниц

meta page (страница 0) - указатель на корень и высоту дерева;
внутренние страницы - разделители и downlink на детей;
листовые страницы - ключ и ссылка ctid на строку.

Поиск: meta → корень → внутренние → лист. Увидеть руками через pageinspect:

sql

SELECT root, level FROM bt_metap('tickets_pkey');

SELECT itemoffset, ctid, data FROM bt_page_items('tickets_pkey', 1);

Почему дерево мелкое

Сбалансированность

§ команды

bash

SELECT root, level FROM bt_metap('idx_name');

Корень и высота B-tree

bash

SELECT * FROM bt_page_items('idx_name', 1);

Содержимое страницы индекса (спуск по дереву)