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

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

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


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](/courses/postgres/kb/selectivity-crossover.md)).

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

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


## Команды

```sql
SELECT root, level FROM bt_metap('idx_name');
```
Корень и высота B-tree

```sql
SELECT * FROM bt_page_items('idx_name', 1);
```
Содержимое страницы индекса (спуск по дереву)


## См. также

- [B-tree: split, дедупликация, INCLUDE](/courses/postgres/kb/btree-internals.md)
- [Operator classes и выбор индекса](/courses/postgres/kb/operator-classes.md)
- [Селективность и точка перелома](/courses/postgres/kb/selectivity-crossover.md)