В чем профит индекса в данном примере?

Question

[Twitt]

Почитал статью на ruhighload про индексы. Цитата оттуда:

Индекс — это и есть отсортированный набор значений.

Если у нас есть 100 миллионов записей в таблице и пришла выборка на поиск по user_id = 99 999 999 (то биш предпоследний элемент). В чем нам даст профит то, что у нас отсортированный набор данных, если мы начнем поиск начиная с id = 1 и в любом случае переберем весь набор данных, чтобы дойти до пользователя с id = 99 999 999?
Может поиск будет идти как-то по другому? Как в данном случае сделать так, чтобы пользователь с таким id нашелся без подвисания таблицы по времени?

Comments

[Максим Федоров]

Цитата оттуда

Не вся цитата

[ayazer]

поиск начиная с первого кортежа на диске будет происходить как-раз при отсутствии индекса. при наличии - это будет пара шагов вглубь по бтри чтоб найти нужную запись.

Answer 1

[Rsa97]

В чем нам даст профит то, что у нас отсортированный набор данных, если мы начнем поиск начиная с id = 1

А вы начните поиск с середины массива, определите, в какой из половин лежат нужные данные (они ведь отсортированы), затем в этой половине снова проверьте середину, и снова, и снова... Получите простейший бинарный поиск или метод деления пополам.
В худшем случае получите log₂100000000 = 27 сравнений.