ART Index

(26/02/2021)

0. Способы реализации индекса в памяти

• Сравнительное дерево (comparison): сравнение значений ключей и их сортировка с последующим хранением в виде дерева;
• Хеш-таблица (hash): после хеширования данные сохраняются в массиве;
• Словарь-дерево (trie): значения ключей разделяются на токены, которые затем упорядочиваются в соответствии с последовательностью и образуют дерево.

Мы используем алгоритм ART для индексации всех данных в памяти, основанный на структуре словаря-дерева.

1. Введение в ART

ART (The Adaptive Radix Tree) — это адаптивное дерево по основанию системы счисления, которое оптимизирует использование пространства на основе Radix tree. Каждый узел имеет разный размер в зависимости от потребностей.

Существует четыре типа внутренних узлов Node: Node4, Node16, Node48 и Node256. Число указывает на количество элементов, которые может содержать узел. Например, Node4 может хранить только 4 элемента, а Node16 — 16 элементов.

Node4 состоит из двух массивов: vector key(4) и vector<Tree*> pointer(4). Массив key содержит 4 элемента, каждый из которых представляет собой байт. Массив pointer хранит указатели на соответствующие поддеревья.

Например, если мы хотим сохранить строку «art», первый уровень дерева будет иметь тип Node4. Первый массив key будет содержать букву «a», а второй массив pointer будет указывать на поддерево, соответствующее букве «a».

Node16 также состоит из двух массивов, но может хранить до 16 элементов.

Узел Node48 имеет два массива, но первый массив может содержать 256 элементов (что охватывает все возможные представления байта), а второй массив — только 48 элементов. Это объясняет название Node48.

Наконец, узел Node256 содержит только один массив vector<Tree*> pointer(256), что позволяет напрямую обращаться к элементам через индексы.

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

2. Механизм управления параллелизмом — ROWEX

ROWEXREAD_OPTIMIZED WRITE EXLUSION — механизм синхронизации, обеспечивающий оптимизацию чтения и взаимное исключение записи.

Основные принципы работы механизма:

• Обеспечение успешного выполнения операций чтения без блокировки. Операции чтения не используют блокировку.
• Перед изменением узла устанавливается блокировка, которая действует только на операции записи.
• Для обеспечения согласованности операций чтения требуется, чтобы операции записи были атомарными. В ART каждый элемент имеет фиксированное место в пространстве, в отличие от B+ деревьев, где происходит перебалансировка и изменение местоположения элементов. Поэтому операции могут быть атомарными.