Part 1: Hash Array Mapped Trie (HAMT)

Дурость с деревьями продолжается. После недели разговором с von Pavlo о прочих особенностях префиксных деревьев, попробовали переписать индексатор для поискового движка с Radix Trie на HAMT - и не ошиблись.

HAMT (Hash Array Mapped Trie) — это дерево для хранения ключей и чего захотите, которое сочетает в себе hash table и trie, где каждое слово(ключ) хешируется, а части от этого хеша используются, чтобы определить путь в дереве.

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

Итак, само HAMT разбито на узлы по уровням, каждый уровень отвечает за часть битов хеша:
- Уровни с узлом Node, которые отвечают чисто за ветвление по дереву.
- Уровень с узлом Terminal, который всегда последний и хранит сами данные.

Собственно, само Trie будет содержать отдельно слайд нод и терминалов.

    bitmap   uint32    // определяет, какие из 32 слотов заняты
    children []nodeptr // плотный (dense) массив указателей на Node или Terminal, где индекс элемента соответствует номеру включенного бита
}

Для этой реализации был выбран обычным strhash32 как самый компромисс между 8 и 64 (с разбегом на 32 для 650к види документов не должно быть много коллизий)

type Terminal struct {
    Entries  []entry // массив cо списками документов по каждому слову
}

Итак, c группами по 5 бит мы получаем 32 / 5 = 6.2 = 7 уровней, где 1-6 уровень состоит из Node, которые хранят bitmap и указатели на дочерние узлы, а последний 7 уровень идет с Terminal. Терминальная нода не участвует в навигации по битам хеша, а хранит реальные данные.

type entry struct {
    key  string
    docs []fts.Documents
}

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

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

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


Как происходит поиск следующей ноды в HAMT:

На каждом уровне ищем следующую ноду. Собственно, как это происходит:
1. Берём через побитовое И младшие 5 бит хеша:

slot := hash & lowerbits

результат (slot) все еще uint32, но c включенными битами только в диапазоне последних 5 бит (а значит там будут значения от 0 до 31)

2. Cдвигаем uint32(1) на slot позиций - получаем маску с включенным битом на нужной позиции:

mask := 1 << (hash & lowerbits) 

3. Побитовым И проверяем, есть ли в битмапе включенный бит на нужной нам позиции:

if node.bitmap & mask == 0 {
    return n, false // слота нет
}

4. Считаем все занятые слоты до нашего индекс в children:

index := bits.OnesCount32(node.bitmap & (mask - 1))

Имея нужных индекс, повторяем с child[index] на каждом последующем уровне, сдвигая хеш на 5 бит:

hash >>= 5

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

#fts #projects #go