Здравствуйте, 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. Насколько данная связка работоспособна, не знаю.
На запросах select someone from table where id = @id все будет быстро, зато select top 10 someone from table where id > @id order by id будет table scan. 
