Использование баз данных ключ-значение в виде набора с постоянными индексами
Поскольку ниже немного длиннее: вот tl;dr; версия: существует ли лучший метод ключ / значение для быстрого поиска ключа и значения, что-то вроде набора на основе хеша с постоянными индексами?
Я заинтересован в мире баз данных ключ-значение и до сих пор не смог понять, как можно эффективно реализовать следующий вариант использования:
Предположим, мы хотим сериализовать некоторые данные и ссылаться на них где-то еще с помощью постоянного уникального целочисленного индекса. Например: Key = unsigned int, Value = MyData.
База данных должна иметь быстрый поиск ключей и обеспечивать уникальность MyData.
Теперь, когда я вставляю новое значение в свою базу данных, я могу назначить ему новый индексный ключ, например, текущий размер базы данных или, чтобы предотвратить столкновения после удаления элементов, я мог бы сохранить некоторый счетчик извне.
Но как мне гарантировать, что я не вставлю одно и то же значение MyData в свою базу данных? Пока что мне кажется, что это невозможно эффективно с базами данных ключ-значение - это правильно? Т.е. я не хочу перебирать всю базу данных только для того, чтобы убедиться, что значение MyData там уже нет...
Какова лучшая практика для реализации этого, тогда?
Для справки: я работаю на KDevelop, где мы используем выше для нашего кеша анализа кода. На самом деле у нас есть пользовательская реализация приведенного выше варианта использования 1. Найдите Bucket и ItemRepository, если вас интересуют внутренние компоненты, и см. 2 для примерного использования ItemRepository.
Но вы, вероятно, согласитесь, что этот код довольно сложен для понимания и, следовательно, сложен в обслуживании. Я хочу сравнить его производительность с альтернативными решениями, которые могут привести к упрощению кода, но только если это не повлечет за собой серьезного снижения производительности. Учитывая шумиху по поводу производительности хранилищ ключей-значений, таких как OpenLDAP MDB, Kyoto Cabinet и LevelDB, я хотел бы начать с этого.
Насколько я понял, в KDevelop есть своего рода гибридная хэш-карта на диске / в памяти, которая периодически сохраняется на диск (что, конечно, может привести к серьезному повреждению данных в случае сбоев и т. Д.).). Элементы хранятся в местоположении на основе их хеш-значения, что, конечно, также позволяет относительно быстро искать значения, пока хеш-функция быстра. Добавленный поворот состоит в том, что вы также получаете некоторый постоянный индекс базы данных, который можно использовать для поиска элементов достаточно эффективно.
Итак, если коротко, как это можно сделать с базой данных ключ / значение, такой как LevelDB, Киотский кабинет, OpenLDAP MDB - как вы это называете?
3 ответа
Похоже, вы хотите делать то же, что и OpenLDAP с индексом равенства. Возможно, это то же самое, что и пример OrientDB, я его не читал.
Основная таблица индексируется монотонно увеличивающимся целочисленным ключом (называемым entryID) и хранит значение данных. Индекс равенства индексируется хэшем значения и хранит список идентификаторов записи, соответствующих хешу. Поскольку хеш может иметь коллизии, просто наличие записи в индексе равенства не доказывает уникальность или дублирование. Вам все еще нужно проверить фактические значения.
Более быстрый / простой подход, если вы используете MDB, BDB или другую базу данных, которая поддерживает дубликаты ключей, - это просто сохранить одну таблицу, используя хеш в качестве ключа. И в MDB, и в BDB существует запрос GET_BOTH, который соответствует ключу и данным для выполнения выборки. Если это успешно, то вы наверняка знаете, что значение уже существует. В противном случае, это позволяет вам сохранять любые значения данных и не беспокоиться о наличии коллизий хешей.
Предостережение: в MDB, использующем дубликаты ключей, размер значений ограничен менее чем половиной страницы на диске.
Если я не пропустил что-то здесь - обычно ваш алгоритм хеширования непротиворечив и обеспечивает один и тот же ключ для тех же данных. Таким образом, вам нужно только найти ключ, чтобы увидеть, существует ли он, или обработать (вероятно, дублирующий ключ) ошибку, которую БД возвращает вам.
afaik Базы ключей / значений могут и будут применять для вас уникальное ограничение значения, т.е. вы получите ошибку, если попытаетесь сохранить уже существующее значение.
Насколько велики ваши строки значений?
Я просто храню их в ключе и позволяю базе данных выполнять всю работу.
Типичным стилем LevelDB, который применяется к большинству хранилищ KV, будет использование пары ключей с префиксом для обозначения типа
например:
Key = 'i' + ID
Value = valueString
Key = 'v' + valueString
Value = ID
В системе, которая должна учитывать несколько одинаковых значений valueStrings, вы должны переместить идентификатор в конец второго ключа
Key = 'v' + valueString + ID
Value = empty