Twitt
@Twitt

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

Почитал статью на ruhighload про индексы. Цитата оттуда:
Индекс — это и есть отсортированный набор значений.

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

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы