Поиск строк в адаптивном радикальном дереве

Question

Я просматривал исследовательскую работу "Дерево адаптивных корней: индексирование ARTful для баз данных основной памяти", у меня был вопрос о том, как вы можете сопоставить строки с ключами узла. Например: если бы у меня было слово: Iota, которое было первичным ключом (идентификатором) одного из кортежей в моей таблице. И мне пришлось искать его по значениям, начинающимся с A, таким как Альфа и Зета. Для простоты рассмотрим только 10 значений: альфа, бета, дельта, гамма, каппа, йота, фи, пси, ро, дзета. Как бы вы пошли на это?

Ссылка на исследовательский документ: https://db.in.tum.de/~leis/papers/ART.pdf

Answer 1

Мне кажется, что статья просто описывает обычную структуру Trie с различными типами внутренних узлов (содержащую 4, 16 или 256 записей и требующую бинарный поиск в меньших случаях). Авторы также, похоже, каким-то образом сжимают цепочки одиночных дочерних узлов.

Я не думаю, что возможно описать структуру очень хорошо с вашими примерами ключей, так как они будут иметь все отдельные записи в корневом узле (который будет иметь тип 16 в статье), за исключением Phi и Psi, где "P" msgstr "запись привела бы к 4 узлу с записями для" h "и" s ". Все оставшиеся записи будут оптимизированы для цепочек с одним узлом.

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