Здесь может быть полезно «префикс B-дерево» или «простой префикс B-дерево».
«Простой префикс B-дерево» немного проще, просто хранится самый короткий префикс, который разделяет два элемента, без попытки устранить избыточность в этих префиксах (например, для «астрономии» и «азимута», он будет хранить просто « как 'и' az ', но не пытайтесь избежать дублирования' a ').
«Префикс B-дерева» близок к тому, что вы описали - что-то вроде дерева, но в структуре B-дерева, чтобы дать хорошие характеристики при хранении в основном на диске. Тем не менее, он предназначен для удаления (большей части) избыточности внутри префиксов, образующих индекс.
Есть еще один вопрос: вам действительно нужно просматривать записи по порядку, или вам просто нужно быстро найти указанную запись? Если последнее достаточно, вы можете вместо этого использовать расширяемое хеширование. Расширяемое хеширование существует (в различных формах) в течение нескольких десятилетий, и все еще работает довольно хорошо. Общая идея довольно проста: хешируйте строки, чтобы создать ключи фиксированной длины, а затем создайте своего рода дерево этих псевдоключов фиксированной длины. Как и с (почти) любым хешем, вы должны быть готовы к столкновениям. Как и в других хеш-таблицах, детали хеширования и разрешения коллизий различаются (хотя, вероятно, не так много, как с расширяемым хешированием, как хеширование в памяти).
Что касается реального использования, то основные СУБД и СУБД-подобные системы используют все вышеперечисленное. Варианты B-дерева, вероятно, наиболее распространены на рынке СУБД общего назначения (например, Oracle или MS SQL Server). Расширяемое хеширование используется в значительном количестве более специализированных продуктов (например, Lotus Domino Server).