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

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

так я гений получается? я так искал данные в массивах еще в конце 90-х, важных два условия - они должны быть отсортированы и нормально распределены.

Вроде это интерполяционным поиском называют...

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

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

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

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

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

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