Как бинарный поиск используется при индексации базы данных

Question

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

Answer 1

Двоичный поиск позволяет вам быстро просмотреть запись по ее ключу, предполагая, что ключи уже отсортированы.Это особенно верно, если количество ключей велико.32 считывания ключей будет достаточно, чтобы найти любой уникальный ключ в наборе из двух миллиардов отсортированных ключей.

Бинарный поиск работает таким образом, потому что каждая попытка поиска сокращает количество записей для поиска пополам.

При этом базы данных обычно используют некоторые другие двоичные данные .структура, такая как b-деревья или красно-черные деревья для выполнения индексации.Использование двоичного дерева устраняет необходимость сортировки списка ключей перед поиском.

Answer 2

Двоичный поиск вычисляет следующую позицию (среднюю точку) на каждом шаге.

Двоичное дерево БД предварительно вычисляет среднюю точку на каждом шаге, пока не достигнет одного элемента.заполнить все средние точки на дереве.когда делают запросы, СУБД ищет дерево.

Answer 3

Каждый раз, когда у вас есть отсортированный список, вы можете использовать двоичный поиск для эффективного поиска по списку. Индексы базы данных представляют собой структуры данных отсортированных данных.