Эффективное хранение внешнего индекса строк

Question

Скажите, что у вас есть большая коллекция с n объектами на диске и каждая имеет строку переменного размера. Каковы распространенные практики эффективных способов создания индекса этих объектов с простым сравнением строк. Хранение целых строк в индексе было бы непомерно высоким в размерах и вводе/выводе, но поскольку диски имеют высокую задержку хранения, то и ссылки не являются хорошей идеей.

Я думал об использовании B-Tree-подобного дизайна с tries, но не смог найти реализацию базы данных с использованием этого подхода. На самом деле, это трудно найти, как крупные базы данных реализовать индексы для строк (это, вероятно, теряется в обширных результатах для информации SQL-уровня.)

ТИА!

EDIT: изменил название от «эффективной внешней сортировки и поиск сохраненных объектов с большими строками» к «эффективного хранение внешнего индекса строки.»

Answer 1

A «префикс B-дерево» или «просто префикс B-дерево», вероятно, будет полезно здесь.

«Простой префикс B-tree» немного проще, просто сохраняя самый короткий префикс, который разделяет два элемента, не пытаясь устранить избыточность в этих префиксах (например, для «астрономии» и «азимута», он будет хранить только 'as' и 'az', но не пытайтесь избежать дублирования 'a').

A «префикс B-дерево» близко к тому, что вы описали - что-то вроде синтаксического дерева, но в структуре B-дерева, чтобы дать хорошие характеристики при хранении, прежде всего, на диске. Тем не менее, он предназначен для удаления (большей части) избыточности в префиксах, которые формируют индекс.

Существует еще один вопрос: действительно ли вы должны пройти через запись в порядке, или же вам просто нужно искать определенную запись быстро? Если последний является адекватным, вы можете использовать расширенное хеширование. Расширяемое хеширование было вокруг (в нескольких разных формах) в течение нескольких десятилетий и все еще работает очень хорошо. Общая идея довольно проста: хешируйте строки для создания ключей фиксированной длины, а затем создайте какое-то дерево этих псевдо-ключей фиксированной длины. Как и в случае (почти) любого хеша, вы должны быть готовы справиться с столкновениями. Как и в других хэш-таблицах, детали хэширования и разрешения конфликтов различаются (хотя, вероятно, не так много с расширяемым хешированием, как хэш-память в памяти).

Что касается реального использования, основные СУБД и СУБД-подобных систем используют все выше. Варианты B-дерева, вероятно, наиболее распространены на рынке СУБД общего назначения (например, Oracle или MS SQL Server).Расширяемое хеширование используется в множестве более специализированных продуктов (например, Lotus Domino Server).

Answer 2

Что вы делаете с объектами?

Если вы работаете с большой системой, которая требует небольшой задержки для обработки множества одновременных запросов, я бы сохранил объекты в базе данных и заботился о сортировке и индексировании. Это было бы намного проще, чем внедрение B-дерева с нуля и, возможно, с его ошибкой.

В СУБД также есть кеширование и различные другие функции, которые могут облегчить вашу жизнь.

Answer 3

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

Если вы, действительно, хотите их отсортировать по цене, откройте для себя "The Art of Computer Programming" штук, которые сортируются и разыскиваются примерно так же подробно, как вы, вероятно, захотите.