Это наиболее распространенные в наше время индексы, для сверх больших баз данных. Фактически это многоуровневые индексы, правда сделанные не потипу индекс на индекс, как мы рассматривали первоначально.

Суть создания такого индекса такова, чтобы за 2, 3 считывания можно было находить нужную запись. Как это делается: Есть какой то корневой индекс Root( в нем номера – 23, 31, 44, они очень разряжены). У них есть идентификация, указатели.

Все номера делятся на три группы, сначала большая разряженность, потом все чаще и чаще.

Каждый отдельный блок проектируется таким образом, чтобы он занимал на диске размер, равный кластеру диска (от 1 до 8 Кбайт). В среднем один блок должен занимать ровно страницу памяти.

Размещается N указателей, и N+1 на следующую страницу, или соседний блок(все это в одном уровне).

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

Если ключ это четырех байтное целое, а указатель это обычно 8 байт, то блок размером 4096 байт может включать примерно N=340 значений ключа.( 4N+8(N+1) <4096). Такая система(такой индекс) типа B дерева, автоматически поддерживает необходимое количество уровней, и обеспечивает автоматическое заполнение указателей, когда появляется новая запись. Стоимость дисковых операций обычно считается пропорциональной числу блоков. Поиск в таком балансированном дереве, когда обычно проверяется не более трех блоков, считается что он эффективнее чем бинарный поиск(когда каждый раз пополам делили). Недостаток такой балансированной структуры заключается в том, что при большом числе именей, даже запас 50% бывает не хватает. Некоторые из сегментов начинают переполняться(каждый из сегментов – 4096 байт, но записи не равномерно заполняются, какие-то сегменты быстрее заполняются, какие-то медленее). Изначально было 3 блока, но записи переполняются, и начинают делиться. Фактически получается что начинают строиться подуровни. И эта структура начинает превращаться из 3 уровней, в более многоуровневую структуру. Начинается работа администратора. Он должен отменить индекс(снять его), и создать его заново. Для этого есть специальные команды. Многие бугалтерские программы делают, чтоб он при загрузке переиндексировался. Иначе теряются индексы, от частых изменений. В SQL серверах это происходит реже, но и там переиндексирование надо делать (переиндексирование –это снять индекс, и создать заново). Появление дополнительных уровней называется РАЗБАЛАСИРОВКОЙ выше критической глубины (depth). В SQL сервере, начиная с версии 2005, предусмотрена специальная команда, позволяющая после её запуска от имени администратора, организовать этот современный БАЛАНСИРОВАННЫЙ ИНДЕКС.

Комментарии запрещены.