Есть ли такая база данных, которая позволяет сделать что-то типа хэш-таблицы. Чтобы по мере роста этой таблицы скорость доступа (для чтения) не росла.
Например, можно было бы сделать таблицу со столбцами 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), т.е. мы выбросили его стоимость на предыдущем шаге совершенно зря.
Здравствуйте, MasterZiv, Вы писали:
MZ>Если при росте N будет расти число партиций, то поиск нужной партиции уже не MZ>O(1),
У меня складывается ощущение, что Вы забываете читать перед ответом. Он не O(1), он O(log p). На практике этот O(log p) оказывается << O(1) (второго слагаемого, которое "поиск в выбранной партиции"). Соответственно, O(log p) + O(1) оказывается практически неотличимым от O(1). Неужели так упорно непонятно?
Ну ладно, объясняю совсем на пальцах. Допустим, у нас в партиции P записей, Т — время поиска среди них нужной. Тогда если у нас P партиций, время поиска будет примерно T + T = 2T, то есть пока партиций меньше, чем записей в партиции, мы можем оценить время доступа как <2T = O(1). Чтобы логарифм стал ролять, партиций должно стать больше, чем записей в партиции.
Сколько же у нас записей в партиции? Ну у меня, например, типичный размер — 50.000.000. Соответственно, чтобы оценка О(1) начала быть неудовлетворительной, нам потребуется таблица на 2.5E15 записей. Как, поди, каждый день с такими работаете? :-D
> У меня складывается ощущение, что Вы забываете читать перед ответом. Он не O(1), > он O(log p).
А ты пиши почаще, чтобы люди не успевали забывать, о чём речь...
На практике этот O(log p) оказывается << O(1) (второго слагаемого, > которое "поиск в выбранной партиции"). Соответственно, O(log p) + O(1) > оказывается практически неотличимым от O(1). Неужели так упорно непонятно?
Неа. Ладно, читаем дальше.
> Ну ладно, объясняю совсем на пальцах. Допустим, у нас в партиции P записей, Т — > время поиска среди них нужной. Тогда если у нас P партиций, время поиска будет > примерно T + T = 2T, то есть пока партиций меньше, чем записей в партиции, мы > можем оценить время доступа как <2T = O(1). Чтобы логарифм стал ролять, партиций > должно стать больше, чем записей в партиции.
Как бы если Nпартициз зависит от Nобщих записей, то из O(Nпартиций) делать
O(1) нельзя. Если это константа -- можно. Всё ж просто...
Лучше бы сказал, как ведётся поиск и конечную полную формулу...
Здравствуйте, objMihail, Вы писали:
M>Есть ли такая база данных, которая позволяет сделать что-то типа хэш-таблицы. Чтобы по мере роста этой таблицы скорость доступа (для чтения) не росла.
Ну, как тебе сказать... На запросах select someone from table where id = @id все будет быстро, зато select top 10 someone from table where id > @id order by id будет table scan.
M>Например, можно было бы сделать таблицу со столбцами Key (string), Value (binary). Возможно ещё для поддержки алгоритма хеширования можно сделать поле hash и вручную туда что-нибудь писать (с клиента).
Можно, да.
M>Я думал использовать SqlServer, но там индексы реализованы через B-деревья, а у них сложность логарифмическая. Может есть какая-нибудь специализированная БД или какой-то способ реализовать чтение с постоянной сложностью на sqlserver?
На SQL Server вышеописанный вариант будет единственно возможным. Остальные мейнстимовые БД (Oracle, FB, MySQL) вроде как поддерживают hash индексы.
Всё, что нас не убивает, ещё горько об этом пожалеет.
Здравствуйте, Ромашка, Вы писали:
Р>Ну, как тебе сказать... На запросах select someone from table where id = @id все будет быстро, зато select top 10 someone from table where id > @id order by id будет table scan.
Делаются два индекса. Один деревянный, другой хешовый.
Здравствуйте, Ромашка, Вы писали:
Р>Здравствуйте, vromanov, Вы писали: V>>Делаются два индекса. Один деревянный, другой хешовый.
Хешовый позволяет быстро получить одну запись по ключу (O(1)). Второй (деревянный) позволяет, например, выдать запись с максимальным значением ключа без фулскана. Если это не нужно, то деревянный индекс можно не создавать.
Здравствуйте, MasterZiv, Вы писали:
MZ>А ты пиши почаще, чтобы люди не успевали забывать, о чём речь...
Пробовал — тогда не успевают понять.
MZ>Как бы если Nпартициз зависит от Nобщих записей, то из O(Nпартиций) делать MZ>O(1) нельзя. Если это константа -- можно. Всё ж просто...
> MZ>Как бы если Nпартициз зависит от Nобщих записей, то из O(Nпартиций) делать > MZ>O(1) нельзя. Если это константа -- можно. Всё ж просто... > > Ok, я понял. Тебе шашечки, мне ехать.
Я-то тут при чём ? И мне как раз ехать, а оно быстрее O(log N) не поедет.
Здравствуйте, objMihail, Вы писали:
M>Есть ли такая база данных, которая позволяет сделать что-то типа хэш-таблицы.
Да. hash-based indexes существуют, и применяются довольно много где. Например, в Оракле. M>Чтобы по мере роста этой таблицы скорость доступа (для чтения) не росла.
Нет. Бесплатного сыра не бывает. Скорость доступа к хеш таблице вовсе не O(1). Точнее, она O(1) только в том случае, если размер таблицы фиксирован. А при фиксированном размере даже линейный перебор будет иметь "асимптотику" O(1).
M>Я думал использовать SqlServer, но там индексы реализованы через B-деревья, а у них сложность логарифмическая. Может есть какая-нибудь специализированная БД или какой-то способ реализовать чтение с постоянной сложностью на sqlserver?
Имхо, вы некорректно ставите вопрос.
Вам нужно
а) Оценить количество записей и его динамику
б) Оценить требования к быстродействию.
На всякий случай напомню очевидное: основание логарифма в B-tree получается обычно очень большим. Скажем, на одну страницу в SQL Server влазит 622 32х-битных ключа. Т.е. мы имеем log(N, 622) чтений для поиска одной из N строк по целочисленному идентификатору.
Из очевидных соображений получаем, что поведение этой функции будет примерно таким:
N от 0 до 622 - одно чтение
N от 623 до 386 884 - два чтения
N от 386 885 до 240 641 848 - три чтения
N от 240 641 849 до 149 679 229 456 - четыре чтения
На самом деле, в 32 бита всунуть 149 миллиардов разных значений не получится. Так что SQL Server достанет любую строку в таблице по целочисленному идентификатору за 4 обращения.
Вы можете провести самостоятельные расчёты и оценить, каков будет разброс времён доступа для ваших параметров задачи.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>На всякий случай напомню очевидное: основание логарифма в B-tree получается обычно очень большим. Скажем, на одну страницу в SQL Server влазит 622 32х-битных ключа. Т.е. мы имеем log(N, 622) чтений для поиска одной из N строк по целочисленному идентификатору. S>Из очевидных соображений получаем, что поведение этой функции будет примерно таким: S>
S>N от 0 до 622 - одно чтение
S>N от 623 до 386 884 - два чтения
S>N от 386 885 до 240 641 848 - три чтения
S>N от 240 641 849 до 149 679 229 456 - четыре чтения
S>
при чем первые два, а то и три уровня дерева будут лежать в кэше СУБД. Так что практически получим O(1)
LD>при чем первые два, а то и три уровня дерева будут лежать в кэше СУБД. Так что практически получим O(1)
Ну, это уже сильно зависит от всяких дополнительных условий. Первый уровень — одна страница; второй — 622, третий — уже таки 386884 страницы. Это 3 гигабайта. Не всякий сервер отдаст три гига под кэш одного индекса.
Но вы правы в том, что в целом зависимостью от N в данном случае можно и пренебречь.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, MasterZiv, Вы писали:
MZ>Да, конечно могут быть "СУБД" работающие in-memory, там такие вещи MZ>делать можно. Примеры не знаю.
Насколько я знаю (к сожалению, только в теории, на практике не пробовал), hash индексы есть в MySQL. Также там есть MEMORY storage engine, которая, как можно догадаться из названия, хранит данные в RAM. Насколько данная связка работоспособна, не знаю.
Здравствуйте, fmiracle, Вы писали:
F>Если размер партиции фиксирован, то при росте N будет расти число партиций,
Будет, конечно. Только стоит ещё подумать, что это значит на практике.
F>Фактически p = N/psize => сложность O( log(N/psize) )
А вот здесь Вы делаете ошибку, отбрасывая главное слагаемое вместо второстепенного. "Фактически" время складывается из "время поиска партиции" + "время поиска внутри партиции". При этом первое — фактически время бинарного поиска в находящемся в памяти массиве небольших размеров. Нужно быть сугубым теоретиком, чтобы всерьёз учитывать эти микросекунды сравнительно со вторым слагаемым.
Ну сами посудите, допустим, делаем партиции по 50 млн. записей. Таких партиций.. 1000.. ну допустим, 10'000. Вот сколько займёт то по сравнению с другим?
Здравствуйте, Softwarer, Вы писали:
S>Ну сами посудите, допустим, делаем партиции по 50 млн. записей. Таких партиций.. 1000.. ну допустим, 10'000. Вот сколько займёт то по сравнению с другим?
ув. Sinclair выше, но я переспрошу: в чём принципиальное отличие от поиска по верхним уровням индекса? Тот же бинарный поиск, тот же массив небольших размеров. В чём разница?
На запросах select someone from table where id = @id все будет быстро, зато select top 10 someone from table where id > @id order by id будет table scan. 
