Что такое база данных с массивом / упорядоченным поиском?

Question

Я ищу базу данных, которая поддерживает следующие функциональные возможности:

1) Записи в базе данных подобны словарям Python или хэшам Perl.Например, запись "покупка" может выглядеть следующим образом:

<purchase 5436> = { product: "BMX Bike", price: 99.50, city: "Springfield" }

2) Записи хранятся в массивах переменной длины.База данных содержит множество таких массивов.Например, таблица покупок может выглядеть следующим образом:

purchase array 1: [ <purchase 5436>, <purchase 54>, <purchase 112> ]
purchase array 2: [ <purchase 76>, <purchase 5984>, <purchase 1102>, <purchase 12> ]
...
purchase array 658: [ <purchase 10142>, <purchase 35>, <purchase 6458>, <purchase 23> ]

3) Я хочу иметь возможность выполнять два вида запросов к этой базе данных:

3a) Подсчитайте количество записей, соответствующих различным критериям.Например, сколько покупок было совершено на сумму более 50?Я знаю множество баз данных, которые поддерживают это.

3b) Подсчитайте, сколько раз записи появлялись в определенном порядке.Например, сколько существует массивов, если была совершена покупка более 50, а затем была совершена покупка в "Спрингфилде"?Я не знаю, какую базу данных вы бы использовали для этого.

Редактировать:Ответ Стиву Хейгу:Я должен был упомянуть, что скорость важна, и эта база данных должна поддерживать гигабайты данных.Например, может быть 1 000 000 000 массивов покупок, и я хочу подсчитать, у скольких из них есть покупка в "Спрингфилде", за которой следует покупка в "Родном городе" (обратите внимание, что порядок важен).Возможно, я ошибаюсь, но я думаю, что реляционная база данных была бы слишком медленной для этой цели.

Answer 1

Вы уверены, что не сможете сделать это с реляционной БД, используя ссылку или соединительную таблицу?

У вас будет столбец заказов, столбец продуктов и таблица order-products, в которой есть строка для каждого продукта для каждого заказа.

я думаю это статья вероятно, выражает лучше, чем я мог бы.

Answer 2

Например, может быть 1 000 000 000 массивов покупок, и я хочу подсчитать, у скольких из них есть покупка в "Спрингфилде", за которой следует покупка в "Родном городе" (обратите внимание, что порядок важен).Может быть, я ошибаюсь, но я думаю, что реляционная база данных была бы слишком медленной для этой цели.

То, что вы описываете, типично хранилище данных запросы, и AFAIK, которые обычно реализуются с использованием реляционных баз данных, хотя и оптимизированных для создания отчетов, а не для параллельной обработки транзакций.Однако я не думаю, что разница в скорости будет чрезмерной, если вы будете использовать "обычную" СУБД.Конечно, если у вас достаточно денег, вы могли бы приобрести специальное хранилище данных СУБД.

Наиболее важным фактором, влияющим на скорость, будет 1) технология, оптимизированная для обработки запросов к большим дисковым наборам данных - это именно то, что предлагают все "реальные" DMBSS, и 2) данные, организованные правильным образом.

3b) Подсчитайте, сколько раз записи появлялись в определенном порядке.Например, сколько существует массивов была ли совершена покупка более 50, а затем была совершена покупка в "Спрингфилде" ?Я не знаю, какую базу данных вы бы использовали для этого.

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

Answer 3

На самом деле вам не нужна реляционная база данных, поскольку у вас есть просто пары ключ->значение, сгруппированные в коллекции, вам понадобятся соединения между двумя таблицами (одна для записей, одна для коллекций) для перебора записей в коллекции и в ваш случай не стоит таких затрат.

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

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

Однако могут быть какие-то запросы, которые вы никогда не сможете выполнить в режиме реального времени за считанные миллисекунды, и тот, что касается поиска покупок с одним условием, за которыми следуют покупки с другим условием, выглядит следующим образом.Либо вы найдете способ поддерживать отслеживание этих чисел в реальном времени при вставке/удалении/изменении, либо вам придется фактически перебирать миллионы массивов, избежать этого невозможно.Вам нужно будет подумать, насколько свежими должны быть ваши данные, и, возможно, каждые несколько часов делать предварительные расчеты, чтобы генерировать эту статистику, а затем иметь возможность получить к ней доступ в O (1) с помощью ключей поиска.

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

Answer 4

Я не уверен, что полностью понимаю, что вы ищете, но вы смотрели диван?.Он ориентирован на документы и не содержит схем.

Answer 5

То, что вы описываете, очень похоже на Свинка даже если у меня есть некоторые сомнения относительно возможности определять запросы, в которых возможен порядок «записей» в массивах.

Посмотрите ссылку, как вы увидите, есть также текущие коммерческие версии.