25 B-дерево

PostgreSQL 18 · Издание 2026 года · Китайский перевод доступен для PostgreSQL 18

简体中文 · PG14 English · PG14 简体中文 · PG18Русский · PG18

25.1. Общий принцип

B-дерево (метод доступа btree) — структура данных, которая позволяет быстро найти нужный элемент в листьях дерева, спускаясь к нему от корня ¹. Чтобы путь поиска был однозначно определен, элементы в дереве должны быть упорядочены. B-дерево предназначено для порядковых типов данных, значения которых можно сравнивать и сортировать.

На схематично показанном индексе, построенном по кодам аэропортов, внутренние узлы изображены горизонтально, а листовые — вертикально:

Рисунок 25.1 Общий принцип

Каждый узел дерева содержит несколько элементов, состоящих из ключа индексирования и ссылки. Элементы внутренних узлов дерева ссылаются на узлы следующего уровня, а элементы листовых узлов — на версии строк таблицы (на рисунке эти ссылки не показаны).

B-деревья обладают несколькими важными свойствами:

Они сбалансированы, то есть все листья находятся на одной глубине. Поэтому поиск любого значения занимает одинаковое время.
Они сильно ветвисты, то есть каждый узел содержит много элементов, часто сотни (на рисунке узлы состоят всего из трех элементов исключительно для наглядности). За счет этого глубина B-деревьев получается небольшой даже для очень больших таблиц.

Примечание

Доподлинно неизвестно, что означает буква «B» в названии дерева. Одинаково хорошо подходит и balanced (сбалансированное), и bushy (ветвистое). Но на удивление часто встречается расшифровка binary (двоичное), которая, конечно, неверна.

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

25.2. Поиск и вставка

Поиск по равенству

Рассмотрим поиск ² значения в дереве по условию «индексированный-столбец = выражение». Допустим, нас интересует аэропорт KJA (Красноярск).

Поиск начинается с корневого узла, и метод доступа должен определить, в какой из дочерних узлов спускаться. Выбирается ключ K_i, для которого верно K_i ⩽ выражение < K_i₊₁.

Рисунок 25.2 Поиск по равенству

В корневом узле находятся ключи AER и OVB. Выполняется условие AER ⩽ ⩽ KJA < OVB, поэтому спускаться надо в дочерний узел, на который ссылается элемент с ключом AER.

Эта процедура повторяется рекурсивно до тех пор, пока мы не дойдем до листового узла, из которого уже можно получить идентификатор версии строки. В данном случае в дочернем узле выполняется условие DME ⩽ KJA < < KZN, поэтому надо спуститься в листовой узел, на который ссылается элемент с ключом DME.

Можно заметить, что во внутренних узлах дерева крайний левый ключ избыточен: чтобы выбрать дочерний узел корня, достаточно выполнения условия KJA < OVB. Такие ключи не хранятся в B-дереве, и на следующих рисунках я буду оставлять соответствующие элементы пустыми.

В листовом узле нужный элемент быстро находится простым двоичным поиском.

В реальности процедура поиска вовсе не так проста, как кажется на первый взгляд. Нужно учитывать, что значения в индексе могут быть упорядочены не только по возрастанию, как на рисунке, но и по убыванию. Даже в уникальном индексе может оказаться несколько подходящих значений, и поиск должен вернуть их все. Причем одинаковых значений может оказаться так много, что они не поместятся в один узел, и тогда поиск придется продолжить в соседней листовой странице. (с. 533)

Примечание

Из-за того, что в индексе могут находиться неуникальные значения, правильнее было бы говорить не «по возрастанию», а «по неубыванию» (и не «по убыванию», а «по невозрастанию»). Я все-таки буду придерживаться более простого варианта. К тому же идентификатор версии строки является частью индексного ключа, что позволяет считать элементы индекса уникальными, даже когда значения совпадают.

Кроме всего прочего, во время поиска другие процессы могут изменять данные, страницы могут расщепляться на две, и дерево может перестраиваться. Все алгоритмы построены таким образом, чтобы эти одновременные действия по возможности не мешали друг другу и не требовали лишних блокировок. Но в эти детали я вдаваться не буду. (v. 12)

Поиск по неравенству

При поиске по условию «индексированный-столбец ⩽ выражение» (или «индексированный-столбец ⩾ выражение») сначала надо найти в индексе значение по условию равенства, а затем двигаться по листовым узлам в нужную сторону до самого конца.

Рисунок 25.3 Поиск по неравенству

Рисунок показывает процесс поиска аэропортов с кодами, меньшими или равными DME (Домодедово).

Для операторов «больше» и «меньше» поиск выполняется так же, надо только исключить исходно найденное значение.

Поиск по диапазону

При поиске по диапазону «выражение₁ ⩽ индексированный-столбец ⩽ выражение₂» сначала надо найти выражение₁, а затем двигаться вправо по листовым узлам до выражения₂.

На рисунке показан процесс поиска аэропортов с кодами от LED (Санкт-Петербург) до ROV (Ростов-на-Дону) включительно.

Рисунок 25.4 Поиск по диапазону

Вставка

Место нового элемента в листовых узлах однозначно определяется порядком расположения ключей. Например, при вставке в таблицу аэропорта с кодом RTW (Саратов) элемент будет добавлен в предпоследний листовой узел между имеющимися ROV и SGC.

Рисунок 25.5 Вставка

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

В данном примере добавление аэропорта TJM привело к расщеплению двух узлов; новые узлы выделены на рисунке. Чтобы можно было расщеплять любые узлы дерева, двунаправленным списком связаны не только узлы нижнего уровня, но и узлы остальных уровней тоже.

Описанная процедура вставок и расщеплений гарантирует сбалансированность дерева, а поскольку в реальности количество элементов в узле обычно велико, наращивание дополнительного уровня происходит редко.

Проблема в том, что расщепленные узлы никогда не объединяются, даже если после очистки в них остается мало элементов. Это ограничение не B-дерева как структуры данных, а реализации PostgreSQL. Поэтому если при вставке узел оказывается заполнен, метод доступа старается в первую очередь очистить узел от лишней информации, чтобы освободить место и не допустить лишнее расщепление. (с. 123)

25.3. Страничная организация

Каждый узел B-дерева занимает одну страницу. Размер страницы и определяет вместимость узла.

Расщепления приводят к тому, что в разные моменты времени корнем дерева могут выступать разные страницы. Но алгоритм поиска должен начинать работу именно с корня. Он находит номер текущей корневой страницы в нулевой странице индекса (называемой метастраницей). Метастраница содержит и некоторую другую служебную информацию.

Рисунок 25.6 Страничная организация

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

Заглянем в страницы настоящего индекса по шестизначным номерам бронирований с помощью расширения pageinspect. В метастранице нас интересует номер корневой страницы и максимальный уровень дерева (уровни нумеруются с нуля, начиная с листьев):

=> SELECT root, level
FROM bt_metap('bookings_pkey');
 root | level
------+-------
  290 |     2
(1 row)

Ключи в индексных записях выводятся как последовательность байтов, что не очень-то удобно. Вот пример:

=> SELECT data
FROM bt_page_items('bookings_pkey',290)
WHERE itemoffset = 2;
          data
-------------------------
 0f 30 43 39 41 42 31 00
(1 row)

Для расшифровки значений придется написать adhoc-функцию. Она будет работать не во всех случаях и не на всех платформах, но годится для примеров в этой главе:

=> CREATE FUNCTION data_to_text(data text)
RETURNS text
AS $$
DECLARE
  raw bytea := ('\x'||replace(data,' ',''))::bytea;
  pos integer := 0;
  len integer;
  res text := '';
BEGIN
  WHILE (octet_length(raw) > pos) LOOP
    len := (get_byte(raw,pos) - 3) / 2;
    EXIT WHEN len <= 0;
    IF pos > 0 THEN
      res := res || ', ';
    END IF;
    res := res || (
      SELECT string_agg( chr(get_byte(raw, i)),'')
      FROM generate_series(pos+1,pos+len) i
    );
    pos := pos + len + 1;
  END LOOP;
  RETURN res;
END;
$$ LANGUAGE plpgsql;

Теперь мы можем посмотреть на содержимое корневой страницы:

=> SELECT itemoffset, ctid, data_to_text(data)
FROM bt_page_items('bookings_pkey',290);
 itemoffset |   ctid   | data_to_text
------------+----------+--------------
          1 | (3,0)    |
          2 | (289,1)  | 0C9AB1
          3 | (575,1)  | 192F03
          4 | (860,1)  | 25D715
          5 | (1145,1) | 32785C
          6 | (1430,1) | 3F0EB8
 ...
         17 | (4565,1) | C993F6
         18 | (4850,1) | D63931
         19 | (5135,1) | E2CB14
         20 | (5420,1) | EF6FEA
         21 | (5705,1) | FC147D
(21 rows)

Первая запись, как я и говорил, не хранит ключ. Столбец ctid содержит ссылки на дочерние страницы.

Допустим, мы ищем бронирование с номером E2D725. В этом случае мы выбираем запись 19, поскольку E2CB14 ⩽ E2D725 < EF6FEA, и спускаемся на страницу 5135.

=> SELECT itemoffset, ctid, data_to_text(data)
FROM bt_page_items('bookings_pkey',5135);
 itemoffset |   ctid   | data_to_text
------------+----------+--------------
          1 | (5417,1) | EF6FEA    ← верхний ключ
          2 | (5132,0) |
          3 | (5133,1) | E2D71D
          4 | (5134,1) | E2E2F4
          5 | (5136,1) | E2EDE7
 ...
        282 | (5413,1) | EF41BE
        283 | (5414,1) | EF4D69
        284 | (5415,1) | EF58D4
        285 | (5416,1) | EF6410
(285 rows)

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

На этой странице мы выбираем запись 3, поскольку E2D71D ⩽ E2D725 < < E2E2F4, и спускаемся на страницу 5133.

=> SELECT itemoffset, ctid, data_to_text(data)
FROM bt_page_items('bookings_pkey',5133);
 itemoffset |    ctid     | data_to_text
------------+-------------+--------------
          1 | (11921,1)   | E2E2F4
          2 | (11919,76)  | E2D71D
          3 | (11919,77)  | E2D725
          4 | (11919,78)  | E2D72D
          5 | (11919,79)  | E2D733
 ...
        364 | (11921,124) | E2E2DB
        365 | (11921,125) | E2E2DF
        366 | (11921,126) | E2E2E5
        367 | (11921,127) | E2E2ED
(367 rows)

Это листовая страница индекса. Первая запись — верхний ключ, а все остальные записи ссылаются на табличные версии строк.

Вот и наше бронирование:

=> SELECT * FROM bookings WHERE ctid = '(11919,77)';
 book_ref |       book_date        | total_amount
----------+------------------------+--------------
 E2D725   | 2017-01-25 04:10:00+03 |     28000.00
(1 row)

Примерно такая работа и выполняется на низком уровне, когда мы запрашиваем бронирование по коду:

=> EXPLAIN (costs off) SELECT *
FROM bookings WHERE book_ref = 'E2D725';
                 QUERY PLAN
---------------------------------------------
 Index Scan using bookings_pkey on bookings
   Index Cond: (book_ref = 'E2D725'::bpchar)
(2 rows)

Компактное хранение дубликатов

Неуникальные индексы могут содержать множество одинаковых ключей со ссылками на разные табличные строки. Поскольку повторяющиеся ключи занимают много места, дубликаты «схлопываются» в одну индексную запись, содержащую ключ и список табличных идентификаторов³. В ряде случаев эта процедура, называемая исключением дубликатов (deduplication), позволяет существенно сократить размер индекса. (v. 13)

Но и уникальные индексы могут содержать дубликаты ключей из-за многоверсионности, поскольку индекс хранит ссылки на все версии табличных строк. С раздуванием индекса из-за ссылок на неактуальные и обычно короткоживущие версии помогает справиться механизм hot-обновлений, но он работает не всегда. В таком случае исключение дубликатов позволяет выиграть время, необходимое для очистки таблицы от неактуальных версий, и сократить количество вынужденных расщеплений страниц. (с. 111)

Чтобы не тратить ресурсы на исключение дубликатов, когда в этом нет необходимости, «схлопывание» выполняется, только когда на листовой странице не хватает места для вставки новой строки. В этом случае ⁴ самоочистка и исключение дубликатов ⁵ могут освободить место и предотвратить ненужное расщепление. Впрочем, если дубликаты возникают редко, механизм исключения можно отключить с помощью параметра хранения deduplicate_items.

Исключение дубликатов может применяться не для всех индексов. Основное ограничение состоит в том, что равенство ключей должно проверяться простым двоичным сравнением внутреннего представления. Далеко не все типы данных можно сравнивать таким образом. Числа с плавающей точкой (float и double precision) имеют два разных представления нуля. Числа с произвольной точностью (numeric) допускают представление одного и того же числа в разных масштабах, а тип jsonb использует такие числа. Не годятся также текстовые типы при использовании недетерминированных правил сортировки⁶, позволяющих представлять одинаковые символы разными последовательностями байтов (стандартные правила сортировки детерминированы).

Кроме того, в настоящее время исключение дубликатов невозможно для составных типов, диапазонов и массивов, а также не работает с include-индексами.

Чтобы проверить, поддерживается ли исключение дубликатов для конкретного индекса, можно заглянуть в поле allequalimage метастраницы:

=> CREATE INDEX ON tickets(book_ref);
=> SELECT allequalimage FROM bt_metap('tickets_book_ref_idx');
 allequalimage
---------------
 t
(1 row)

В данном случае исключение дубликатов поддерживается. И действительно, на одной из листовых страниц мы видим, что некоторые индексные записи содержат единственный табличный идентификатор (htid), а некоторые — список идентификаторов (tids):

=> SELECT itemoffset, htid, left(tids::text,27) tids,
  data_to_text(data) AS data
FROM bt_page_items('tickets_book_ref_idx',1)
WHERE itemoffset > 1;
 itemoffset |    htid    |            tids             |  data
------------+------------+-----------------------------+--------
          2 | (32965,40) |                             | 000004
          3 | (47429,51) |                             | 00000F
          4 | (3648,56)  | {"(3648,56)","(3648,57)"}   | 000010
          5 | (6498,47)  |                             | 000012
 ...
        271 | (21492,46) |                             | 000890
        272 | (26601,55) | {"(26601,55)","(26601,56)"} | 0008AC
        273 | (25669,37) |                             | 0008B6
(272 rows)

Компактное хранение внутренних индексных записей

Исключение дубликатов позволяет разместить больше записей в листовых страницах индекса. Но для предотвращения лишних расщеплений уплотнение информации во внутренних страницах играет не меньшую роль. Основной объем индекса составляют листовые страницы, но эффективность поиска в индексе напрямую зависит от глубины дерева. (v. 12)

Индексные записи во внутренних страницах содержат ключи индексирования, но их значения используются только для определения поддерева, в которое надо спускаться при поиске. В составных индексах для этого часто достаточно только первого атрибута ключа или нескольких первых. Остальные атрибуты могут быть отброшены, чтобы не занимать место на странице.

Процедура исключения некоторых атрибутов (suffix truncation) выполняется, когда происходит расщепление листовой страницы и во внутренней странице необходимо разместить новую ссылку⁷.

Примечание

В принципе, можно пойти еще дальше и оставлять только значимую часть атрибута, например несколько первых символов строки, достаточных для различения поддеревьев. Но это пока не реализовано: атрибут или целиком остается в индексной записи, или полностью исключается из нее.

Для примера — несколько записей корневой страницы индекса, построенного на таблице билетов по номеру бронирования и имени пассажира:

=> CREATE INDEX tickets_bref_name_idx
ON tickets(book_ref, passenger_name);
=> SELECT itemoffset, ctid, data_to_text(data)
FROM bt_page_items('tickets_bref_name_idx',229)
WHERE itemoffset BETWEEN 8 AND 13;
 itemoffset |   ctid   |        data_to_text
------------+----------+----------------------------
          8 | (1607,1) | 1A98A0
          9 | (1833,2) | 1E57D1, SVETLANA MAKSIMOVA
         10 | (2054,1) | 220797
         11 | (2282,1) | 25DB06
         12 | (2509,2) | 299FE4, YURIY AFANASEV
         13 | (2736,1) | 2D62C9
(6 rows)

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

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

25.4. Сортировка и составные индексы

Порядок столбцов

Порядок, в котором столбцы перечисляются при создании индекса, крайне важен, поскольку данные внутри страниц будут отсортированы сначала по первому столбцу, затем по второму и так далее. Как правило, эффективный поиск в таком индексе возможен по условиям на непрерывную последовательность столбцов, начиная с самого первого: по одному первому, по первому и второму, с первого по третий и так далее. При этом все остальные условия используются только для фильтрации значений, найденных по основным критериям⁸.

Вот порядок индексных записей в первой листовой странице индекса, созданного ранее на таблице билетов по номеру бронирования и по имени пассажира:

=> SELECT itemoffset, data_to_text(data)
FROM bt_page_items('tickets_bref_name_idx',1)
WHERE itemoffset > 1;
 itemoffset |        data_to_text
------------+-----------------------------
          2 | 000004, PETR MAKAROV
          3 | 00000F, ANNA ANTONOVA
          4 | 000010, ALEKSANDR SOKOLOV
          5 | 000010, LYUDMILA BOGDANOVA
          6 | 000012, TAMARA ZAYCEVA
 ...
        189 | 00040C, DMITRIY FEDOROV
        190 | 00041E, EGOR FEDOROV
        191 | 00041E, ILYA STEPANOV
        192 | 000447, VIKTOR VASILEV
        193 | 00044D, NADEZHDA KULIKOVA
(192 rows)

В этом случае эффективный поиск билетов возможен либо по номеру бронирования и имени пассажира, либо только по номеру бронирования:

=> EXPLAIN (costs off) SELECT *
FROM tickets
WHERE book_ref = '000010';
                    QUERY PLAN
--------------------------------------------------
 Index Scan using tickets_book_ref_idx on tickets
   Index Cond: (book_ref = '000010'::bpchar)
(2 rows)
=> EXPLAIN (costs off) SELECT *
FROM tickets
WHERE book_ref = '000010' AND passenger_name = 'LYUDMILA BOGDANOVA';
                             QUERY PLAN
---------------------------------------------------------------------
 Index Scan using tickets_bref_name_idx on tickets
   Index Cond: ((book_ref = '000010'::bpchar) AND (passenger_name...
(2 rows)

Но для поиска только по имени пассажира придется перебрать все строки:

=> EXPLAIN (costs off) SELECT *
FROM tickets
WHERE passenger_name = 'LYUDMILA BOGDANOVA';
                         QUERY PLAN
-------------------------------------------------------------
 Gather
   Workers Planned: 2
   -> Parallel Seq Scan on tickets
       Filter: (passenger_name = 'LYUDMILA BOGDANOVA'::text)
(4 rows)

И наоборот, если создать индекс по именам и по номерам бронирования, эффективно будут поддерживаться запросы по имени или одновременно по имени и по номеру бронирования:

=> CREATE INDEX tickets_name_bref_idx
ON tickets(passenger_name, book_ref);
=> SELECT itemoffset, data_to_text(data)
FROM bt_page_items('tickets_name_bref_idx',1)
WHERE itemoffset > 1;
 itemoffset |         data_to_text
------------+------------------------------
          2 | ADELINA ABRAMOVA, E37EDB
          3 | ADELINA AFANASEVA, 1133B7
          4 | ADELINA AFANASEVA, 4F3370
          5 | ADELINA AKIMOVA, 7D2881
 ...
        185 | ADELINA LEBEDEVA, 0A00E3
        186 | ADELINA LEBEDEVA, DAEADE
        187 | ADELINA LEBEDEVA, DFD7E5
        188 | ADELINA LOGINOVA, 8022F3
        189 | ADELINA LOGINOVA, EE67B9
        190 | ADELINA LUKYANOVA, 292786
        191 | ADELINA LUKYANOVA, 54D3F9
(190 rows)
=> EXPLAIN (costs off) SELECT * FROM tickets
WHERE passenger_name = 'LYUDMILA BOGDANOVA';
                           QUERY PLAN
-----------------------------------------------------------------
 Bitmap Heap Scan on tickets
   Recheck Cond: (passenger_name = 'LYUDMILA BOGDANOVA'::text)
   -> Bitmap Index Scan on tickets_name_bref_idx
       Index Cond: (passenger_name = 'LYUDMILA BOGDANOVA'::text)
(4 rows)

Оптимизация пропуска

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

Представим себе таблицу, которая показывает, на каких авиалиниях эксплуатируются самолеты. Ее первый столбец route_type имеет всего два возможных значения: D (внутренние линии, domestic) и I (международные, international). Второй столбец aircraft_code хранит код модели. Некоторые самолеты летают только внутри страны, некоторые — только за рубеж, а часть используется на любых рейсах. На первом и втором столбцах построен индекс.

Чтобы разобраться с оптимизацией пропуска, предположим сначала, что мы сумели добавить к условию aircraft_code = '733' еще одно: route_type = ANY('{D,I}'). Индексное сканирование эффективно учтет такое условие благодаря тому, что B-дерево поддерживает свойство SEARCH ARRAY. Сначала поиск в индексе выполняется по условию route_type = 'D' AND aircraft_code = '733': (с. 411)

Рисунок 25.7 Оптимизация пропуска

Затем выполняется еще один поиск, теперь по условию route_type = 'I' AND aircraft_code = '733':

Рисунок 25.8 Оптимизация пропуска

С точки зрения планировщика оба поиска в индексе происходят в рамках одного индексного сканирования, поэтому в плане выполнения будет один узел Bitmap Index Scan. Посмотрим на реальном запросе:

=> CREATE INDEX ON flights(status, aircraft_code);
=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM flights
WHERE status IN ('Arrived', 'Cancelled', 'Delayed',
                 'Departed', 'On Time', 'Scheduled')
  AND aircraft_code = '733';
                             QUERY PLAN
---------------------------------------------------------------------
 Bitmap Heap Scan on flights (actual rows=8263.00 loops=1)
   Recheck Cond: (((status)::text = ANY ('{Arrived,Cancelled,Dela...
   Heap Blocks: exact=133
   Buffers: shared hit=136 read=14
   -> Bitmap Index Scan on flights_status_aircraft_code_idx (actu...
       Index Cond: (((status)::text = ANY ('{Arrived,Cancelled,De...
       Index Searches: 3
       Buffers: shared hit=3 read=14
(8 rows)

Строка Index Searches показывает количество поисков в индексе. В данном случае сканирование потребовало всего три спуска от корня к листьям, а не шесть, поскольку строки с четырьмя статусами оказались удачно локализованы на одной странице данных:

=> SELECT itemoffset, ctid, data_to_text(data)
FROM bt_page_items('flights_status_aircraft_code_idx',174)
WHERE data_to_text(data) LIKE '% 733';
 itemoffset |   ctid    |  data_to_text
------------+-----------+----------------
          6 | (24,8207) | Cancelled, 733
         15 | (1015,64) | Delayed, 733
         22 | (24,8194) | Departed, 733
         30 | (24,8214) | On Time, 733
(4 rows)

Нерелевантные части индекса при таком сканировании пропускаются, поэтому операция и называется оптимизацией пропуска, или skip scan. Это не отдельный вид сканирования, а именно оптимизация, которая работает с любым индексным доступом (Index Scan, Index Only Scan, Bitmap Index Scan).

Что же происходит, когда условие на первый столбец не указано? Оценить количество уникальных значений можно по статистике, но полагаться на статистику для получения точного списка, конечно, нельзя. (с. 351)

Итак, мы хотим выполнить запрос к таблице по условию aircraft_code = '733'. Нам неизвестно наименьшее значение route_type, но его можно получить из самой первой записи самой первой листовой страницы индекса:

Рисунок 25.9 Оптимизация пропуска

Теперь мы знаем, что первое значение столбца route_type равно D, и можем выполнить второй поиск по условию на оба столбца: route_type = 'D' AND aircraft_code = '733'.

Рисунок 25.10 Оптимизация пропуска

Мы нашли первое подходящее значение. Если бы на прочитанной листовой странице оказалась запись с другим значением первого столбца, мы бы знали следующее точное условие. В данном случае нам не повезло, поэтому приходится выполнить поиск по условию route_type > 'D':

Рисунок 25.11 Оптимизация пропуска

На найденной листовой странице не оказалось нужной записи, но мы узнали второе значение столбца route_type. Поэтому выполняем следующий поиск по условию route_type = 'I' AND aircraft_code = '733':

Рисунок 25.12 Оптимизация пропуска

Сканирование можно завершать, поскольку мы добрались до последней листовой страницы индекса. В противном случае пришлось бы выполнить еще один поиск — по условию route_type > 'I', — чтобы убедиться, что других значений нет.

Запрос без условия на первый столбец потребовал немного больше поисков в индексе и прочитал немного больше страниц, чем предыдущий вариант, но все же выполнился весьма эффективно:

=> EXPLAIN (analyze, costs off, timing off, summary off)
SELECT * FROM flights
WHERE aircraft_code = '733';
                             QUERY PLAN
---------------------------------------------------------------------
 Bitmap Heap Scan on flights (actual rows=8263.00 loops=1)
   Recheck Cond: (aircraft_code = '733'::bpchar)
   Heap Blocks: exact=133
   Buffers: shared hit=154 read=4
   -> Bitmap Index Scan on flights_status_aircraft_code_idx (actu...
       Index Cond: (aircraft_code = '733'::bpchar)
       Index Searches: 4
       Buffers: shared hit=21 read=4
(8 rows)

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

Конечно, приведенный пример не претендует на полноту описания. В частности, в некоторых случаях начатый поиск может продолжаться на соседних листовых страницах в надежде на то, что в них обнаружится подходящая индексная запись. Это позволяет укрупнить отдельные обращения к индексу и уменьшить их количество, экономя на спуске от корня к листовым узлам⁹.

Другой пример: для дискретных типов данных в классе операторов B-дерева можно определить опорную функцию, которая сообщит минимальное и максимальное значения данного типа и функции для перехода к следующему и предыдущему значениям¹⁰. Благодаря этой информации отыскивать очередное значение в индексе не потребуется; сканирование сможет сразу перейти к его проверке.

Направление сортировки

При создании индекса нужно учитывать не только порядок столбцов, но и порядок сортировки. По умолчанию значения упорядочены по возрастанию (ASC), но можно указать и обратный порядок (DESC). В индексе по одному столбцу это не играет особой роли, поскольку индекс можно сканировать в любую сторону. Но в составном индексе порядок важен.

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

=> EXPLAIN (costs off) SELECT *
FROM tickets ORDER BY passenger_name, book_ref;
                    QUERY PLAN
---------------------------------------------------
 Index Scan using tickets_name_bref_idx on tickets
(1 row)
=> EXPLAIN (costs off) SELECT *
FROM tickets ORDER BY passenger_name DESC, book_ref DESC;
                         QUERY PLAN
------------------------------------------------------------
 Index Scan Backward using tickets_name_bref_idx on tickets
(1 row)

Но из этого индекса невозможно сразу же получить данные, которые по одному столбцу будут отсортированы по возрастанию, а по другому — по убыванию. Индекс поставляет частично упорядоченные данные, которые затем сортируются по второму атрибуту (здесь и далее для простоты отключены параллельные планы): (с. 498)

=> EXPLAIN (costs off) SELECT *
FROM tickets ORDER BY passenger_name ASC, book_ref DESC;
                       QUERY PLAN
--------------------------------------------------------
 Incremental Sort
   Sort Key: passenger_name, book_ref DESC
   Presorted Key: passenger_name
   -> Index Scan using tickets_name_bref_idx on tickets
(4 rows)

На возможность использовать индекс для сортировки влияет и расположение неопределенных значений. По умолчанию для целей сортировки неопределенные значения считаются «больше» обычных значений, то есть располагаются с правого конца дерева при сортировке по возрастанию или с левого при сортировке по убыванию. Этот порядок можно менять с помощью предложений NULLS LAST и NULLS FIRST.

В следующем примере индекс не удовлетворяет предложению ORDER BY, и результат приходится сортировать:

=> EXPLAIN (costs off) SELECT *
FROM tickets ORDER BY passenger_name NULLS FIRST, book_ref DESC;
                      QUERY PLAN
-------------------------------------------------------
 Sort
   Sort Key: passenger_name NULLS FIRST, book_ref DESC
   -> Seq Scan on tickets
(3 rows)

Но если создать индекс, соответствующий желаемому порядку, он будет использоваться:

=> CREATE INDEX tickets_name_bref_idx2
ON tickets(passenger_name NULLS FIRST, book_ref DESC);
=> EXPLAIN (costs off) SELECT *
FROM tickets ORDER BY passenger_name NULLS FIRST, book_ref DESC;
                     QUERY PLAN
----------------------------------------------------
 Index Scan using tickets_name_bref_idx2 on tickets
(1 row)

25.5. Класс операторов

Семантика сравнения

Системе необходимо уметь не только хешировать значения, но и упорядочивать значения разных типов, в том числе пользовательских. Это требуется для сортировок и группировок, соединения слиянием и некоторых других операций. И так же, как для хеширования, соответствие между типом данных и операторами сравнения задается классом операторов¹¹.

Класс операторов позволяет не привязываться к именам (таким как >, <, =) и даже иметь несколько способов упорядочить значения одного и того же типа.

Вот какие операторы сравнения должны быть заданы в любом классе операторов метода btree (на примере семейства bool_ops): (psql: \dAo)

=> SELECT amopopr::regoperator AS opfamily_operator,
  amopstrategy
FROM pg_am am
  JOIN pg_opfamily opf ON opfmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opf.oid
WHERE amname = 'btree'
AND opfname = 'bool_ops'
ORDER BY amopstrategy;
  opfamily_operator  | amopstrategy
---------------------+--------------
 <(boolean,boolean)  |            1
 <=(boolean,boolean) |            2
 =(boolean,boolean)  |            3
 >=(boolean,boolean) |            4
 >(boolean,boolean)  |            5
(5 rows)

Здесь мы видим пять операторов сравнения. Каждый из них соответствует одной из стратегий¹², которая определяет его семантику:

меньше;
меньше либо равно;
равно;
больше либо равно;
больше.

Класс операторов B-дерева включает также несколько опорных функций¹³. Первая из них должна возвращать единицу, если ее первый аргумент больше второго, минус единицу — если меньше, и ноль — если аргументы равны.

Остальные опорные функции необязательны, но позволяют методу доступа работать более производительно.

Чтобы лучше разобраться в этом механизме, полезно создать новый тип данных и установить для него порядок сортировки, отличный от порядка по умолчанию. Документация приводит такой пример для комплексных чисел¹⁴, но использует язык C. К счастью, класс операторов для B-дерева можно создать и с помощью интерпретируемых языков, чем я и воспользуюсь, чтобы сделать этот пример как можно более простым (хотя и заведомо неэффективным).

Создадим новый составной тип для единиц измерения информации:

=> CREATE TYPE capacity_units AS ENUM (
  'B', 'kB', 'MB', 'GB', 'TB', 'PB'
);
=> CREATE TYPE capacity AS (
  amount integer,
  unit capacity_units
);

Теперь создадим таблицу со столбцом нового типа и заполним ее случайными значениями:

=> CREATE TABLE test AS
  SELECT ( (random()*1023)::integer, u.unit )::capacity AS cap
  FROM generate_series(1,100),
    unnest(enum_range(NULL::capacity_units)) AS u(unit);

По умолчанию значения составных типов сортируются в лексикографическом порядке, который в данном случае не совпадает с естественным порядком:

=> SELECT * FROM test ORDER BY cap;
    cap
-----------
 (1,MB)
 (2,kB)
 (3,MB)
 (7,GB)
 ...
 (1018,TB)
 (1020,B)
 (1020,kB)
 (1021,PB)
(600 rows)

Создание класса операторов начнем с функции, которая пересчитывает объем в байты:

=> CREATE FUNCTION capacity_to_bytes(a capacity) RETURNS numeric
AS $$
SELECT a.amount::numeric *
  1024::numeric ^ ( array_position(enum_range(a.unit), a.unit) - 1 );
$$ LANGUAGE sql STRICT IMMUTABLE;
=> SELECT capacity_to_bytes('(1,kB)'::capacity);
 capacity_to_bytes
--------------------
 1024.0000000000000
(1 row)

Затем создадим опорную функцию для будущего класса операторов:

=> CREATE FUNCTION capacity_cmp(a capacity, b capacity)
RETURNS integer
AS $$
SELECT sign(bookings.capacity_to_bytes(a) - bookings.capacity_to_bytes(b));
$$ LANGUAGE sql STRICT IMMUTABLE;

Теперь с помощью опорной функции легко определить операторы сравнения. Я специально использую «странные» имена, чтобы показать, что они могут быть произвольными:

=> CREATE FUNCTION capacity_lt(a capacity, b capacity) RETURNS boolean
AS $$
BEGIN
  RETURN capacity_cmp(a,b) < 0;
END;
$$ LANGUAGE plpgsql IMMUTABLE STRICT;
=> CREATE OPERATOR #<# (
  LEFTARG = capacity,
  RIGHTARG = capacity,
  FUNCTION = capacity_lt
);

Остальные четыре оператора определяются по аналогии.

=> CREATE FUNCTION capacity_le(a capacity, b capacity) RETURNS boolean
AS $$
BEGIN
  RETURN capacity_cmp(a,b) <= 0;
END;
$$ LANGUAGE plpgsql IMMUTABLE STRICT;
=> CREATE OPERATOR #<=# (
  LEFTARG = capacity,
  RIGHTARG = capacity,
  FUNCTION = capacity_le
);

=> CREATE FUNCTION capacity_eq(a capacity, b capacity) RETURNS boolean
AS $$
BEGIN
  RETURN capacity_cmp(a,b) = 0;
END;
$$ LANGUAGE plpgsql IMMUTABLE STRICT;
=> CREATE OPERATOR #=# (
  LEFTARG = capacity,
  RIGHTARG = capacity,
  FUNCTION = capacity_eq,
  MERGES -- можно использовать в соединении слиянием
);

=> CREATE FUNCTION capacity_ge(a capacity, b capacity) RETURNS boolean
AS $$
BEGIN
  RETURN capacity_cmp(a,b) >= 0;
END;
$$ LANGUAGE plpgsql IMMUTABLE STRICT;
=> CREATE OPERATOR #>=# (
  LEFTARG = capacity,
  RIGHTARG = capacity,
  FUNCTION = capacity_ge
);

=> CREATE FUNCTION capacity_gt(a capacity, b capacity) RETURNS boolean
AS $$
BEGIN
  RETURN capacity_cmp(a,b) > 0;
END;
$$ LANGUAGE plpgsql IMMUTABLE STRICT;
=> CREATE OPERATOR #># (
  LEFTARG = capacity,
  RIGHTARG = capacity,
  FUNCTION = capacity_gt
);

На этом этапе мы уже можем правильно сравнивать объемы:

=> SELECT (1,'MB')::capacity #># (512, 'kB')::capacity;
 ?column?
----------
 t
(1 row)

А после создания класса операторов заработает как надо и сортировка:

=> CREATE OPERATOR CLASS capacity_ops
DEFAULT FOR TYPE capacity -- будет использоваться по умолчанию
USING btree AS
  OPERATOR 1 #<#,
  OPERATOR 2 #<=#,
  OPERATOR 3 #=#,
  OPERATOR 4 #>=#,
  OPERATOR 5 #>#,
  FUNCTION 1 capacity_cmp(capacity,capacity);
=> SELECT * FROM test ORDER BY cap;
    cap
-----------
 (9,B)
 (30,B)
 (42,B)
 (47,B)
 ...
 (999,PB)
 (1007,PB)
 (1015,PB)
 (1021,PB)
(600 rows)

Наш класс операторов используется по умолчанию при создании индексов, а созданный индекс возвращает значения в правильном порядке:

=> CREATE INDEX ON test(cap);
=> SELECT * FROM test WHERE cap #<# (100,'B')::capacity ORDER BY cap;
  cap
--------
 (9,B)
 (30,B)
 (42,B)
 (47,B)
 (66,B)
 (67,B)
 (69,B)
 (97,B)
 (99,B)
(9 rows)
=> EXPLAIN (costs off)
SELECT * FROM test WHERE cap #<# (100,'B')::capacity ORDER BY cap;
                 QUERY PLAN
---------------------------------------------
 Index Only Scan using test_cap_idx on test
   Index Cond: (cap #<# '(100,B)'::capacity)
(2 rows)

Предложение MERGES, указанное при создании оператора равенства, разрешает использовать соединение слиянием для значений нашего типа. (с. 483)

25.6. Свойства

Посмотрим интерфейсные свойства B-деревьев. (с. 404)

Свойства уровня метода доступа

=> SELECT a.amname, p.name, pg_indexam_has_property(a.oid, p.name)
FROM pg_am a, unnest(array[
  'can_order', 'can_unique', 'can_multi_col',
  'can_exclude', 'can_include'
]) p(name)
WHERE a.amname = 'btree';
 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 btree  | can_order     | t
 btree  | can_unique    | t
 btree  | can_multi_col | t
 btree  | can_exclude   | t
 btree  | can_include   | t
(5 rows)

B-дерево может упорядочивать данные и поддерживает уникальность. Это единственный метод доступа, который обеспечивает такие свойства.

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

Поддержка ограничений исключения формально есть, но ограничивается оператором равенства, что соответствует требованию уникальности. Вместо такого ограничения гораздо лучше использовать настоящее полноценное ограничение уникальности.

B-дерево позволяет также добавлять в индекс дополнительные столбцы, не участвующие в поиске.

Индекс будет строиться в параллельном режиме, если таблица достаточно велика. Количество рабочих процессов определяется по той же формуле, что и для параллельного последовательного сканирования, но ограничено сверху значением параметра max_parallel_maintenance_workers. На все рабочие процессы выделяется объем памяти размером maintenance_work_mem. (с. 384) (по умолчанию: 2) (по умолчанию: 64MB)

Рабочие процессы параллельно сканируют таблицу и сортируют полученные данные ¹⁵; результат образует листовые страницы индекса, над которыми затем надстраиваются внутренние страницы вплоть до корня.

Свойства уровня индекса

=>  SELECT p.name, pg_index_has_property('flights_pkey', p.name)
FROM unnest(array[
  'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan'
]) p(name);
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | t
 index_scan    | t
 bitmap_scan   | t
 backward_scan | t
(4 rows)

Индекс на основе B-дерева можно использовать для кластеризации.

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

=> EXPLAIN (costs off) SELECT *
FROM bookings ORDER BY book_ref DESC;
                     QUERY PLAN
-----------------------------------------------------
 Index Scan Backward using bookings_pkey on bookings
(1 row)

Свойства уровня столбца

Свойство ORDERABLE говорит о том, что B-дерево хранит данные упорядоченно, и первые четыре свойства (ASC и DESC, NULLS FIRST и NULLS LAST) определяют, как именно они упорядочены для данного столбца. В следующем примере значения столбца отсортированы по возрастанию, а неопределенные значения находятся в конце.

=> SELECT p.name,
  pg_index_column_has_property('flights_pkey', 1, p.name)
FROM unnest(array[
  'asc', 'desc', 'nulls_first', 'nulls_last', 'orderable',
  'distance_orderable', 'returnable', 'search_array', 'search_nulls'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 asc                | t
 desc               | f
 nulls_first        | f
 nulls_last         | t
 orderable          | t
 distance_orderable | f
 returnable         | t
 search_array       | t
 search_nulls       | t
(9 rows)

Свойство SEARCH NULLS показывает возможность поиска неопределенных значений.

Для B-деревьев не реализована поддержка операторов упорядочивания (DISTANCE ORDERABLE), хотя такие попытки предпринимались¹⁶.

B-деревья поддерживают поиск нескольких значений из массива (свойство SEARCH ARRAY) и позволяют получать данные без обращения к таблице (RETURNABLE).

postgrespro.ru/docs/postgresql/18/btree; backend/access/nbtree/README. ↩︎
backend/access/nbtree/nbtsearch.c, функция _bt_search. ↩︎
postgrespro.ru/docs/postgresql/18/btree#BTREE-DEDUPLICATION. ↩︎
backend/access/nbtree/nbtinsert.c, функция _bt_delete_or_dedup_one_page. ↩︎
backend/access/nbtree/nbtdedup.c, функция _bt_dedup_pass. ↩︎
postgrespro.ru/docs/postgresql/18/collation. ↩︎
backend/access/nbtree/nbtinsert.c, функция _bt_split. ↩︎
postgrespro.ru/docs/postgresql/18/indexes-multicolumn. ↩︎
backend/access/nbtree/nbtutils.c, функция _bt_advance_array_keys. ↩︎
include/utils/skipsupport.h. ↩︎
postgrespro.ru/docs/postgresql/18/btree#BTREE-BEHAVIOR. ↩︎
postgrespro.ru/docs/postgresql/18/xindex#XINDEX-STRATEGIES. ↩︎
postgrespro.ru/docs/postgresql/18/btree-support-funcs. ↩︎
postgrespro.ru/docs/postgresql/18/xindex#XINDEX-EXAMPLE. ↩︎
backend/access/nbtree/nbtsort.c, функция btbuild. ↩︎
commitfest.postgresql.org/27/1804. ↩︎