Описание предложенной структуры
В статье предложена структура данных для хранения множества строк K, которую в дальнейшем мы будем называть BST (Block String Trie), и над которой определены следующие (словарные) операции:
- insert(s) — добавить строку s в множество K;
- delete(s) — удалить строку s из множества K;
- find(s) — найти все строки в K с префиксом s, включая саму строку s.
Данная структура данных, как видно, сама по себе не предусматривает хранения пар "ключ/значение". Учитывая наши требования, мы будем хранить значения как части физически сохраняемого ключа. Рассмотрим пример. Пусть надо сохранить пару (k,v). Для этого мы строим строковый ключ k’=k+c+string(v), где под c понимается символ, которого нет в алфавите символов логических ключей (так, для текстовых строк можно использовать нулевой символ), а string(v) — любое строковое представление значения. Если надо найти все значения, соответствующие некоторому ключу k, необходимо вызвать find(k+c).
В нашей структуре данных мы разделяем несколько уровней объединения вершин дерева. Внутренние вершины дерева объединяются в ветки, а ветки целиком хранятся в страницах внешней памяти. Ниже мы опишем последовательно эти уровни.
