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

B-tree: split, дедупликация, INCLUDE

При переполнении страница делится (split), разделитель поднимается вверх; high key и right link дают параллельный доступ. Дедупликация хранит повтор один раз с posting list; suffix truncation обрезает разделители; INCLUDE покрывает запрос.

view as markdownaka: btree-split, btree-deduplication, suffix-truncation

Механизмы, делающие B-tree компактным и параллельным (структура - в btree-structure).

Split и right link

Когда в листовую страницу некуда вставить ключ, она делится: половина записей уезжает в новую страницу, разделитель поднимается в родителя. Split корня повышает дерево на уровень. Для параллельного доступа без блокировки дерева используется приём Лемана-Яо: на каждой странице есть high key (верхняя граница) и right link на правого соседа. Если ключ уехал вправо при split, поиск догоняет его по right link.

Дедупликация

Повторяющиеся ключи хранятся один раз с posting list из всех ctid:

(done → [ctid1, ctid2, ctid3, ...])

Резко уменьшает индекс на колонках с малым числом различных значений.

Suffix truncation

Разделители во внутренних страницах обрезаются до различающего префикса - fanout растёт, дерево ещё мельче.

INCLUDE

sql

CREATE INDEX ON tickets (flight_id) INCLUDE (passenger);

Payload-колонки в листе под Index-Only Scan: не часть ключа, не нагружают спуск, но доступны для чтения из индекса. Применение - в index-design.

§ команды

bash

CREATE INDEX ON t (key) INCLUDE (payload);

Покрывающий индекс под Index-Only Scan

bash

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

Увидеть записи с posting list (дедупликация)

§ см. также

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

B-tree: split, дедупликация, INCLUDE

view as markdownaka: btree-split, btree-deduplication, suffix-truncation

Механизмы, делающие B-tree компактным и параллельным (структура - в btree-structure).

Split и right link

Дедупликация

Повторяющиеся ключи хранятся один раз с posting list из всех ctid:

(done → [ctid1, ctid2, ctid3, ...])

Резко уменьшает индекс на колонках с малым числом различных значений.

Suffix truncation

Разделители во внутренних страницах обрезаются до различающего префикса - fanout растёт, дерево ещё мельче.

INCLUDE

sql

CREATE INDEX ON tickets (flight_id) INCLUDE (passenger);

§ команды

bash

CREATE INDEX ON t (key) INCLUDE (payload);

Покрывающий индекс под Index-Only Scan

bash

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

Увидеть записи с posting list (дедупликация)