Разреженный / Плотный индекс и как он работает?

Question

Я могу понять, как работает индекс B*Tree, выполнив поиск по дереву.

Но я не могу понять, как работает разреженный индекс или плотный индекс.

Например, если для плотного индекса необходимо, чтобы каждое значение отображалось с помощью ключа. Какая польза от поиска?

Добавляем больше разъяснений:
Этот запасной / плотный индекс ссылается на индекс, описанный здесь на вики: https://en.wikipedia.org/wiki/Database_index

Насколько я понимаю, смысл работы индекса заключается в том, что вы можете искать в B*Tree как O(logN) вместо того, чтобы искать каждый блок как O(N)

Но, из описания либо разреженного индекса, либо плотного индекса. Я не вижу, как это выгодно для поиска, вы ищете по ключам? Но ключи имеют то же количество, что и значения, верно? (для плотного индекса это строго равно)

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

Answer 1

Разреженный индекс на уровне блоков

Разреженный индекс на уровне блоков будет полезен только для запросов, где индекс также кластеризован (т. Е. Порядок сортировки индекса представляет расположение данных на диске). Разреженный индекс на уровне блока будет иметь меньше значений, но все же будет полезен для поиска приблизительного местоположения перед началом последовательного сканирования. Разреженность в этом случае фактически является "индексом каждого n- го значения в кластерном индексе".

С точки зрения поиска запрос разреженного индекса на уровне блоков будет:

• найти самый большой ключ, который меньше или равен вашим индексированным критериям поиска O(log N) для поиска)
• используйте этот ключ в качестве отправной точки для последовательного сканирования кластерного индекса (O(N) для поиска)

Преимущество разреженного индекса блочного уровня заключается, главным образом, в размере, а не в скорости: меньший разреженный индекс может уместиться в память, когда плотный индекс (включая все значения) не будет. Запросы на основе диапазонов в кластеризованном индексе уже будут возвращать последовательные результаты, поэтому разреженный индекс может иметь некоторые преимущества, если индекс не слишком разрежен для эффективной поддержки общих запросов.

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

Рабочий пример см. В разделе Плотные и разреженные индексы (sfu.ca).

MongoDB индекс с sparse вариант

до сих пор я не могу понять, как работает разреженный индекс в MongoDB. Например, у вас есть N значений с полем x не пустым. тогда у вас будет N ключей. Тогда как ключ поможет вам в поиске?

Индекс MongoDB с sparse Опция содержит записи только для документов, имеющих индексированное поле. MongoDB имеет гибкую схему, поэтому поля не обязательно должны присутствовать (или одного типа) для всех документов в коллекции. Примечание: дополнительная проверка документов является функцией MongoDB 3.2+.

По умолчанию все документы в коллекции будут включены в индекс, но те, у которых нет индексированного поля, будут хранить null значение. Если все ваши документы в коллекции MongoDB имеют значение для индексированного поля, нет разницы между индексом по умолчанию и индексом с sparse вариант.

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

Документация MongoDB вызывает это с примечанием:

Не путайте разреженные индексы в MongoDB с индексами блочного уровня в других базах данных. Думайте о них как о плотных индексах с определенным фильтром.