Как можно построить индекс базы данных поверх хранилища ключей / значений?

Question

Я читал о LevelDB и обнаружил, что:

В следующих версиях браузера Chrome реализована реализация HTML5 API IndexedDB, построенного поверх LevelDB

.

IndexedDB также является простым хранилищем ключей / значений, которое может индексировать данные.

Мой вопрос: как можно построить индекс поверх хранилища ключей / значений? Я знаю, что индекс на самом низком уровне - это n-арное дерево, и я понимаю, как данные индексируются в базе данных. Но как можно использовать хранилище ключей / значений, например LevelDB, для создания индекса базы данных?

Answer 1

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

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

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

Answer 2

Еще пара вещей, LevelDB поддерживает сортировку данных с помощью пользовательского компаратора со страницы , на которую вы ссылаетесь :

По данным сайта проекта ключевые особенности:

• Ключи и значения являются произвольными байтовыми массивами.
• Данные хранятся отсортированными по ключу.
• Вызывающие могут предоставить пользовательскую функцию сравнения для переопределения порядка сортировки.
• ....

Таким образом, LevelDB может содержать данные, которые могут быть отсортированы / проиндексированы на основе 1 порядка сортировки.

Если вам нужно несколько индексируемых полей, вы можете просто добавить свое собственное B-дерево, которое работает поверх LevelDB. Я полагаю, что именно такой подход использует браузер Chrome, но я просто догадываюсь.

Вы всегда можете просмотреть источник Chrome .