Здравствуйте, fmiracle, Вы писали:

F>Если размер партиции фиксирован, то при росте N будет расти число партиций,

Будет, конечно. Только стоит ещё подумать, что это значит на практике.

F>Фактически p = N/psize => сложность O( log(N/psize) )

А вот здесь Вы делаете ошибку, отбрасывая главное слагаемое вместо второстепенного. "Фактически" время складывается из "время поиска партиции" + "время поиска внутри партиции". При этом первое — фактически время бинарного поиска в находящемся в памяти массиве небольших размеров. Нужно быть сугубым теоретиком, чтобы всерьёз учитывать эти микросекунды сравнительно со вторым слагаемым.

Ну сами посудите, допустим, делаем партиции по 50 млн. записей. Таких партиций.. 1000.. ну допустим, 10'000. Вот сколько займёт то по сравнению с другим?

Здравствуйте, Softwarer, Вы писали:

S>Ну сами посудите, допустим, делаем партиции по 50 млн. записей. Таких партиций.. 1000.. ну допустим, 10'000. Вот сколько займёт то по сравнению с другим?

Это уже писал

Автор: Sinclair
Дата: 29.08.12

ув. Sinclair выше, но я переспрошу: в чём принципиальное отличие от поиска по верхним уровням индекса? Тот же бинарный поиск, тот же массив небольших размеров. В чём разница?