Двоичный поиск против вероятностного

[nin-jin]

С поиском-то всё понятно, а как быть с добавлением данных? Повсеместно используемый в СУБД B-tree использует букеты, выстраивая их в самобалансирующееся дерево, что неизбежно приводит к логарифмическому поиску. Причём далеко не бинарному, то есть степень логарифма не 2, а исчисляется десятками, а то и сотнями. Предложенный же тут алгоритм работает лишь на плоских списках. А если его применять к не плоским, то вновь выползет логарифм на доступ к каждому элементу. Для равномерно распределённых данных таким образом лучше подходит какой-нибудь trie, который по префиксу очень быстро скачет по букетам, и поиск в котором для фиксированной длины ключа даёт константную сложность.

[janatem]

Причём далеко не бинарному, то есть степень логарифма не 2, а исчисляется десятками, а то и сотнями.

Так наоборот же — чем больше основание логарифма, тем лучше, быстрее получается. Собственно, основная фишка этих B-tree состоит в том, чтобы сделать деревья пошире и уменьшить глубину.

[nin-jin]

О том и речь..

[yrub]

может равномерно?)

[yappari]

Надо полагать, что это не принципиально, коль скоро известен закон распределения (аналитическая запись).

[yrub]

Датасеты состояли из отсортированных случайных целых чисел, что может служить достаточно точным представлением наших данных.

может служить, а может и нет. помню на это как-то обращал внимание Миловидов, что для тестов базы лучше брать реальные данные, а не рандомные, по крайне мере для строк

[VADemon]

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

[h1pp0]

Выше уже писали, что это похоже на интерполяционный поиск. Добавлю:

• Это старый метод, у Кнута уже был.

• Асимптотика известна, это не константа, а O(log log N)

• В чистом виде обычно не применяется, но может быть полезен на первых X шагах, потом уже двоичный.