Прежде всего, необходимо уточнить, что мой рассказ не заменяет книг и статей про сбалансированные сильно ветвистые деревья (B-tree), а дополняет эти знания практическим примером. Теперь ближе к делу. Создам в PostgreSQL таблицу с очень простой структурой и напишу функцию для генерации случайных данных. Далее выполню запрос, который возвращает количество значений, соответствующих показанному условию. Для этого СУБД потребуется пройтись по всем страницам и проверить каждое значение на равенство. Такой подход не очень рационален. Мы выполняем много медленных дисковых операций и много шагов по страницам. Создадим индекс и повторим запрос. Видно, что теперь СУБД использовала поиск по индексу, что существенно уменьшило количество шагов и увеличило скорость работы запроса. Разумеется, упомянутый индекс нельзя называть двоичным (бинарным) деревом, так как он имеет очень много ветвлений, следовательно, даже в больших таблицах глубина дерева обычно составляет от трёх до пяти уровней.