Индексы баз данных деревья

Индексы баз данных деревья

PostgreSQL поддерживает несколько типов индексов: B-дерево, хеш, GiST, SP-GiST, GIN, BRIN и расширение bloom. Для разных типов индексов применяются разные алгоритмы, ориентированные на определённые типы запросов. По умолчанию команда CREATE INDEX создаёт индексы-B-деревья, эффективные в большинстве случаев. Выбрать другой тип можно, написав название типа индекса после ключевого слова USING . Например, создать хеш-индекс можно так:

CREATE INDEX имя ON таблица USING HASH (столбец);

11.2.1. B-дерево

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

При обработке конструкций, представимых как сочетание этих операторов, например BETWEEN и IN , так же может выполняться поиск по индексу-B-дереву. Кроме того, такие индексы могут использоваться и в условиях IS NULL и IS NOT NULL по индексированным столбцам.

Также оптимизатор может использовать эти индексы в запросах с операторами сравнения по шаблону LIKE и ~ , если этот шаблон определяется константой и он привязан к началу строки — например, col LIKE ‘foo%’ или col ~ ‘^foo’ , но не col LIKE ‘%bar’ . Но если ваша база данных использует не локаль C, для поддержки индексирования запросов с шаблонами вам потребуется создать индекс со специальным классом операторов; см. Раздел 11.10. Индексы-B-деревья можно использовать и для ILIKE и ~* , но только если шаблон начинается не с алфавитных символов, то есть символов, не подверженных преобразованию регистра.

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

11.2.2. Хеш

Хеш-индексы хранят 32-битный хеш-код, полученный из значения индексированного столбца, поэтому хеш-индексы работают только с простыми условиями равенства. Планировщик запросов может применить хеш-индекс, только если индексируемый столбец участвует в сравнении с оператором = . Создать такой индекс можно следующей командой:

CREATE INDEX имя ON таблица USING HASH (столбец);

11.2.3. GiST

GiST-индексы представляют собой не просто разновидность индексов, а инфраструктуру, позволяющую реализовать много разных стратегий индексирования. Как следствие, GiST-индексы могут применяться с разными операторами, в зависимости от стратегии индексирования (класса операторов). Например, стандартный дистрибутив PostgreSQL включает классы операторов GiST для нескольких двумерных типов геометрических данных, что позволяет применять индексы в запросах с операторами:

(Эти операторы описаны в Разделе 9.11.) Классы операторов GiST, включённые в стандартный дистрибутив, описаны в Таблице 68.1. В коллекции contrib можно найти и другие классы операторов GiST, реализованные как отдельные проекты. За дополнительными сведениями обратитесь к Главе 68.

GiST-индексы также могут оптимизировать поиск « ближайшего соседа » , например такой:

SELECT * FROM places ORDER BY location point '(101,456)' LIMIT 10;

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

11.2.4. SP-GiST

Индексы SP-GiST, как и GiST, предоставляют инфраструктуру, поддерживающую различные типы поиска. SP-GiST позволяет организовывать на диске самые разные несбалансированные структуры данных, такие как деревья квадрантов, k-мерные и префиксные деревья. Например, стандартный дистрибутив PostgreSQL включает классы операторов SP-GiST для точек в двумерном пространстве, что позволяет применять индексы в запросах с операторами:

(Эти операторы описаны в Разделе 9.11.) Классы операторов SP-GiST, включённые в стандартный дистрибутив, описаны в Таблице 69.1. За дополнительными сведениями обратитесь к Главе 69.

Индексы SP-GiST, как и GiST, поддерживают поиск ближайших соседей. Для классов операторов SP-GiST, поддерживающих упорядочивание по расстоянию, соответствующий оператор указан в столбце « Операторы упорядочивания » в Таблице 69.1.

11.2.5. GIN

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

Подобно GiST и SP-GiST, индексы GIN могут поддерживать различные определённые пользователем стратегии и в зависимости от них могут применяться с разными операторами. Например, стандартный дистрибутив PostgreSQL включает класс операторов GIN для массивов, что позволяет применять индексы в запросах с операторами:

(Эти операторы описаны в Разделе 9.19.) Классы операторов GIN, включённые в стандартный дистрибутив, описаны в Таблице 70.1. В коллекции contrib и в отдельных проектах можно найти и много других классов операторов GIN. За дополнительными сведениями обратитесь к Главе 70.

11.2.6. BRIN

BRIN-индексы (сокращение от Block Range INdexes, Индексы зон блоков) хранят обобщённые сведения о значениях, находящихся в физически последовательно расположенных блоках таблицы. Поэтому такие индексы наиболее эффективны для столбцов, значения в которых хорошо коррелируют с физическим порядком столбцов таблицы. Подобно GiST, SP-GiST и GIN, индексы BRIN могут поддерживать определённые пользователем стратегии и в зависимости от них применяться с разными операторами. Для типов данных, имеющих линейный порядок сортировки, записям в индексе соответствуют минимальные и максимальные значения данных в столбце для каждой зоны блоков. Это позволяет поддерживать запросы со следующими операторами:

Классы операторов BRIN, включённые в стандартный дистрибутив, описаны в Таблице 71.1. За дополнительными сведениями обратитесь к Главе 71.

Источник

Индексируемое бинарное дерево

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

• вставить новый элемент
• удалить элемент по порядковому номеру
• получить элемент по порядковому номеру
• данные хранятся в сортированном виде

Данные постоянно добавляются и удаляются, структура должна обеспечивать быструю скорость работы. Сначала пытался реализовать такую вещь используя стандартные контейнеры из std. Этот путь не увенчался успехом и пришло понимание, что нужно реализовывать что-то самому. Единственное что пришло на ум, это использовать бинарное дерево поиска. Поскольку оно отвечает требованию быстрой вставки, удалению и хранению данных в сортированном виде. Осталось только придумать как проиндексировать все элементы и пересчитывать индексы когда дерево меняется.

В статье будет больше картинок и теории чем кода. Код можно будет посмотреть по ссылке внизу.

Вес

Для этого дерево подверглось небольшой модифицикации, добавилась дополнительная информация о весе узла. Вес узла это кол-во потомков данного узла + 1 (вес единичного элемента).

Функция получения веса узла:

uint64_t bntree::get_child_weight(node_t *node) < if (node) < return node->weight; > return 0; >

У листа соответственно вес равен 0.

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

Когда дерево у нас пусто, то его вес равен 0. Добавим в него корневой элемент:

Вес дерева становится 1, вес корневого элемента 1. Вес корневого элемента является весом дерева.

Добавим еще несколько элементов:

Каждый раз когда идет добавление нового элемента, мы спускаемся по узлам в низ и увеличиваем счетчик веса каждого пройденного узла. При создании нового узла ему выставляется вес 1. Если узел с таким ключом уже существует, то перезапишем значение и пойдем назад до корня вверх отменяя изменения весов у всех узлов которые мы прошли.
Если идет удаление узла, то мы спускается вниз и декрементируем веса пройденных узлов.

Индексы

Теперь перейдем к тому как проиндексировать узлы. Узлы явно не хранят свой индекс, он вычисляется на основе веса узлов. Если бы они хранили свой индекс, то требовалось бы O(n) времени, что бы обновить индексы всех узлов после каждого изменения дерева.
Перейдем к наглядному представлению. Наше дерево пусто, добавим в него 1-ый узел:

Первый узел имеет индекс 0, а теперь возможны 2-а случая. В первом индекс корневого элемента изменится, во втором не изменится.

У корня левое поддерево весит 1.

Индекс корня не изменился, поскольку вес его левого поддерева остался 0.

Как считается индекс узла, это вес его левого поддерева + число переданное от родителя. Что это за число?, Это счетчик индексов, изначально он равен 0, т.к. у корня нет родителя. Дальше все зависит от того куда мы спускаемся к левому ребенку или правому. Если к левому, то к счетчику ни чего не прибавляется. Если к правому то прибавляем индекс текущего узла.

К примеру как вычисляется индекс элемента с ключом 8 (правый ребенок корня). Это «Индекс корня» + «вес левого поддерева узла с ключом 8» + «1» == 3 + 2 + 1 == 6
Индексом элемента с ключом 6 будет «Индекс корня» + 1 == 3 + 1 == 4

Соответственно что бы получить, удалить элемент по индексу требуется время O(log n), поскольку что бы получить нужный элемент мы должны сначала его найти (спуститься от корня до этого элемента).

Глубина

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

Код приведения веса к глубине.

/* * Возвращает первое число в степени 2, которое больше или ровно x */ uint64_t bntree::cpl2(uint64_t x) < x = x - 1; x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); x = x | (x >> 32); return x + 1; > /* * Двоичный логарифм от числа */ long bntree::ilog2(long d) < int result; std::frexp(d, &result); return result - 1; >/* * Вес к глубине */ uint64_t bntree::weight_to_depth(node_t *p) < if (p == NULL) < return 0; >if (p->weight == 1) < return 1; >else if (p->weight == 2) < return 2; >return this->ilog2(this->cpl2(p->weight)); >

Итоги

• вставка нового элемента происходит за O(log n)
• удаление элемента по порядковому номеру происходит за O(log n)
• получение элемента по порядковому номеру происходит за O(log n)

Скоростью O(log n) платим за то, что все данные хранятся в сортированном виде.

Где может пригодиться такая структура — не знаю. Просто задачка, что бы еще раз разобраться как работают деревья. Спасибо за внимание.

Ссылки

В проекте содержатся тестовые данные для проверки скорости работы. Дерево заполняется 1000000 элементов. И происходит последовательное удаление, вставка и получение элементов 1000000 раз. То есть 3000000 операций. Результат оказался вполне неплохим ~ 8 секунд.

Источник