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

_Индексы · PostgreSQL Knowledge Base_

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


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

## 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](/courses/postgres/kb/index-design.md).


## Команды

```sql
CREATE INDEX ON t (key) INCLUDE (payload);
```
Покрывающий индекс под Index-Only Scan

```sql
SELECT * FROM bt_page_items('idx', 1);
```
Увидеть записи с posting list (дедупликация)


## См. также

- [B-tree: структура и спуск](/courses/postgres/kb/btree-structure.md)
- [Проектирование индексов](/courses/postgres/kb/index-design.md)
- [Operator classes и выбор индекса](/courses/postgres/kb/operator-classes.md)