Есть ли такая база данных, которая позволяет сделать что-то типа хэш-таблицы. Чтобы по мере роста этой таблицы скорость доступа (для чтения) не росла.
Например, можно было бы сделать таблицу со столбцами Key (string), Value (binary). Возможно ещё для поддержки алгоритма хеширования можно сделать поле hash и вручную туда что-нибудь писать (с клиента).
Я думал использовать SqlServer, но там индексы реализованы через B-деревья, а у них сложность логарифмическая. Может есть какая-нибудь специализированная БД или какой-то способ реализовать чтение с постоянной сложностью на sqlserver?
Здравствуйте, objMihail, Вы писали:
M>Есть ли такая база данных, которая позволяет сделать что-то типа хэш-таблицы. Чтобы по мере роста этой таблицы скорость доступа (для чтения) не росла.
M>Например, можно было бы сделать таблицу со столбцами Key (string), Value (binary). Возможно ещё для поддержки алгоритма хеширования можно сделать поле hash и вручную туда что-нибудь писать (с клиента).
M>Я думал использовать SqlServer, но там индексы реализованы через B-деревья, а у них сложность логарифмическая. Может есть какая-нибудь специализированная БД или какой-то способ реализовать чтение с постоянной сложностью на sqlserver?
Посмотри в сторону Redis, просто key-value хранилище
Здравствуйте, objMihail, Вы писали:
M>Есть ли такая база данных, которая позволяет сделать что-то типа хэш-таблицы. Чтобы по мере роста этой таблицы скорость доступа (для чтения) не росла.
BerkeleyDB.
> Есть ли такая база данных, которая позволяет сделать что-то типа хэш-таблицы. > Чтобы по мере роста этой таблицы скорость доступа (для чтения) не росла.
все врут в топике. Нет такой СУБД.
Все реализуют O(log N), но это, если подумать, немногим хуже O(1).
Хэш-таблицы невыгодно применять во внешней памяти, потому что
они могут терять эффективность за счёт статистически неподходящих
данных и их надо рехэшировать, а во внешнем хранилище это смерть.
B+tree ненамного хуже по производительности но намного стабильнее
в работе.
Да, конечно могут быть "СУБД" работающие in-memory, там такие вещи
делать можно. Примеры не знаю.
согласен. MZ>Да, конечно могут быть "СУБД" работающие in-memory, там такие вещи MZ>делать можно. Примеры не знаю.
могу ошибаться, но моему memcached, правда под задачи ТС он не подходит.
У хэш таблицы есть минусы. Это рехэширование. Хоть и не часто но зато скопом. Даже если данные находятся в памяти, все равно будут тормоза при доступе к данным которые лежат вне кэша.
Вот сравнение. В которых Б+ деревья сливают всего в 4 раза. http://rsdn.ru/article/alg/tlsd.xml
Здравствуйте, objMihail, Вы писали:
M>Я думал использовать SqlServer, но там индексы реализованы через B-деревья, а у них сложность логарифмическая. Может есть какая-нибудь специализированная БД или какой-то способ реализовать чтение с постоянной сложностью на sqlserver?
Такой способ существует, думаю, уже давно во всех основных СУБД, называется "партиционирование".
Здравствуйте, MasterZiv, Вы писали:
MZ>Это не O(1), это MZ>p O( log N/p ) , где p -- число партиций. MZ>вместо O( log N )
(скучая) Во-первых, партиционирование бывает разное. Вы написали формулу, немного смахивающую на формулу для хэш-партиционирования, но зачем-то множите на p вместо O(1). Во-вторых, для типичного случая range-партиционирования формула принимает вид O(log p) + O(1), где p — количество партиций. На практике это не имеет заметных отличий от O(1) + O(1).
On 08/16/2012 11:05 AM, Softwarer wrote:
> (скучая) Во-первых, партиционирование бывает разное. Вы написали формулу, > немного смахивающую на формулу для хэш-партиционирования, но зачем-то множите на > p вместо O(1).
Ну да.
Во-вторых, для типичного случая range-партиционирования формула > принимает вид O(log p) + O(1), где p — количество партиций. На практике это не
Здравствуйте, MasterZiv, Вы писали:
>> Ну на самом деле О(1), но чтобы формально правильно. Есть упорядоченный набор >> партиций, сколько времени занимает поиск нужной? MZ>log p. MZ>Ну а потом -то надо ещё внутри партиции искть, или как ?
Нужно, конечно. И занимает это О(1) времени. Как и любая операция над данными фиксированного размера.
> Нужно, конечно. И занимает это О(1) времени. Как и любая операция над данными > фиксированного размера.
Ничего не перепутал ?
Может тогда сразу: "размер таблицы N записей. N фиксировано, поэтому результат
поиска одной из N записй будет O(1)"
В партиции-то как искать запись будем ?
Posted via RSDN NNTP Server 2.1 beta
Re[4]: Чтение записей из базы со коростью O(1)
От:
Аноним
Дата:
20.08.12 04:45
Оценка:
S> для типичного случая range-партиционирования формула принимает вид O(log p) + O(1), где p — количество партиций. На практике это не имеет заметных отличий от O(1) + O(1).
Мне понравился твой фокус. Теперь ты следи за руками — принимаем p=1 (одна партиция == обычная база данных) и получаем O(1) + O(1) на любой базе данных Вывод: партиционирование не нужно?
S>(скучая)
Здравствуйте, Softwarer, Вы писали:
>>> Ну на самом деле О(1), но чтобы формально правильно. Есть упорядоченный набор >>> партиций, сколько времени занимает поиск нужной? MZ>>log p. MZ>>Ну а потом -то надо ещё внутри партиции искть, или как ?
S>Нужно, конечно. И занимает это О(1) времени. Как и любая операция над данными фиксированного размера.
Если размер партиции фиксирован, то при росте N будет расти число партиций, и значит p зависит от N, и значит нельзя O( log p ) свести к O(1)
Фактически p = N/psize => сложность O( log(N/psize) )
> Если размер партиции фиксирован, то при росте N будет расти число партиций, и > значит p зависит от N, и значит нельзя O( log p ) свести к O(1) > Фактически p = N/psize => сложность O( log(N/psize) )
Если при росте N будет расти число партиций, то поиск нужной партиции уже не
O(1), т.е. мы выбросили его стоимость на предыдущем шаге совершенно зря.
Да, не сходятся у него концы с концами.
Чем зря спорить ни о чём, я предлагаю описать подробнее,
что за партицирование имеется в виду, структуры данных
и базовые алгоритмы, и таким образом будет хотя бы видно,
что имеется в виду и какие там должны быть O().
Что до начала дискуссии, я лично более чем удовлетворён
тем, что мы всегда можем иметь O(log N) и я сам лично
имел счастье наблюдать разницу в 12 порядков между
числом записей в БД и временем выполнения запроса
(поиск по селективному индексу).
Т.е. представьте десятки миллиардов записей в БД и
запрос, выполняющийся за несколько десятков милисекунд.
Это очень здорово, мне лично никакого O(1) не нужно.
>> Если размер партиции фиксирован, то при росте N будет расти число партиций, и >> значит p зависит от N, и значит нельзя O( log p ) свести к O(1) >> Фактически p = N/psize => сложность O( log(N/psize) )
MZ>Если при росте N будет расти число партиций, то поиск нужной партиции уже не MZ>O(1), т.е. мы выбросили его стоимость на предыдущем шаге совершенно зря.
