Почему блоки переполнения в базе данных не доступны для двоичного поиска? - PullRequest
0 голосов
/ 03 октября 2009

Это связано с основным механизмом индексации базы данных (разреженная индексация).

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

Может ли кто-нибудь объяснить, как блоки переполнения делают невозможным использование бинарного поиска?

1 Ответ

2 голосов
/ 03 октября 2009

Блоки переполнения создаются, когда в индексированном блоке недостаточно места для создания новой записи.

Блоки переполнения не могут быть подвергнуты двоичному поиску, поскольку они не являются частью первичной схемы индексации / связанного списка (то есть не двоичной индексации). Вместо этого они присоединяются к (связанным с) первичным блокам, которые являются частью схемы индексации.

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

Если вы хотите, вы можете проиндексировать блоки переполнения, чтобы сделать их гражданами первого класса (часть двоичного поиска), но тогда они больше не будут блоки переполнения.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...