Битовый индекс является дополнительной структурой данных к основной,
отображающей значения индексируемого атрибута на набор идентификаторов записей.
В целом определение такое же, как и у простого индекса, но набор идентификаторов
записей формируется иначе. Если в случае простого индекса хранятся значения
идентификаторов и, вообще говоря, они могут быть произвольными, в том числе
строками или составными, то в случае битовых индексов идентификаторы
рассматриваются строго как целые числа.
Набором идентификаторов является битовая последовательность, в которой идентификатору строки соответствует положение бита в соответствии с его величиной. Наличие записи с заданным значением атрибута отмечается 1, отсутствие - 0 или пустым хвостом. Положим, что есть три записи:
Операции получения идентификаторов строк по значениям атрибутов сводятся к использованию битовых операций с битовыми картами и выборке из получившейся битовой карты позиций ненулевых битов. Значения этих позиций считаются идентификаторами строк.
К особенностям битовых индексов относится то, что они могут быть, как и простые индексы, составными, но не могут быть кластерными. Другим ограничением является то, что идентификатором строки данных должно быть строго натуральное число. В большинстве систем второе ограничение совершенно незаметно, поскольку идентификаторы и без того поддерживаются в автоинкрементном режиме.
Битовые индексы и простые индексы по одной и той же таблице могут быть совмещены. Но если для таблицы используется кластерный индекс, то битовый индекс для нее уже не может быть применен, поскольку идентификатор строки фактически нечисловой. Совмещение и одновременное применение простых и битовых индексов выполняется алгоритмически. Также может быть организована многоиндексная выборка совместно из нескольких простых и битовых индексов.
Небольшой пример реализации битового индекса:
Также строится только одна битовая карта. В реальном приложении, несмотря на то, что хранится только один бит на запись, битовые карты должны быть сегментированы, поскольку работа с неограниченными строками обычно не предусматривается. Разбиение по сегментам выполняется вычислением номера сегмента и позиции в сегменте по значению идентификатора. В системе должна быть выбрана одна и та же гранулярность сегмента, чтобы битовые логические операции выполнялись корректно. Точное значение размера битового сегмента, вообще говоря, лучше определять экспериментально. Об этом пойдет речь в части сравнения битовых и простых индексов.
Простой пример сегментирования битового индекса:
В действительности, это тоже еще не все - у реализации битовых функций в Cach'e и MiniM есть техническая особенность - нельзя использовать нулевое число в качестве позиции в сегменте (третий параметр). При этом число ноль получается для идентификаторов, кратных размеру сегмента. Чтобы избежать этой проблемы, можно поступить просто - после вычисления правильной позиции в сегменте к ней прибавить единицу, например, и во всех функциях, использующих сегменты, учитывать эту неправильную единицу. Например:
К недостаткам битовых индексов относятся необходимость применения битовых операций к всей битовой карте независимо от того, сколько реально там содержится значимых бит. Поскольку в большинстве случаев процессы обращаются к объектам в относительно небольшом диапазоне идентификаторов, вероятность что эти идентификаторы находятся в одном сегменте увеличивается. В случае же уменьшения величины сегмента битовый индекс по структуре и характеристикам приближается к простому обратному списку. В ситуации "размер сегмента равен единице" битовый индекс полностью вырождается в обычный.
К как преимуществам, так и недостаткам битовых индексов, в зависимости от характера их применения может быть отнесено сочетание их реализации с транзакционностью прикладной системы. Для отдельных реализаций битовых индексов транзакционность системы будет негативным фактором, для других она не имеет значения. Более подробной этот вопрос описывается в главе о транзакциях.
В любом случае выбор вида индекса оставим за программистом и руководителем проекта. Отметим, что сейчас мы занимаемся только техническими вопросами, на основе которых и можно сделать аргументированный выбор. В документации и рекомендациях фирм - производителей движков баз данных также можно найти советы по выбору применяемых индексов. Важно понимать, на основе чего они сделаны, каковы характеристики движков этих баз данных и для каких характерных операций этот выбор предлагается.
Подробнее о книге "MUMPS СУБД"
Набором идентификаторов является битовая последовательность, в которой идентификатору строки соответствует положение бита в соответствии с его величиной. Наличие записи с заданным значением атрибута отмечается 1, отсутствие - 0 или пустым хвостом. Положим, что есть три записи:
1 шарик красный 12 2 шарик синий 5 3 кубик красный 7 4 кубик синий 3В этом случае есть 4 идентификатора, их значения рассматриваются как позиции битов в битовой карте. В карте получается в данном случае 4 бита. По атрибуту фигура два различных значения, поэтому в этом индексе будет две карты. То же самое по атрибуту цвет.
Индекс по фигуре значение атрибута биты 0 1 2 3 4 шарик 0 1 1 0 0 кубик 0 0 0 1 1 Индекс по цвету значение атрибута биты 0 1 2 3 4 красный 0 1 0 1 0 синий 0 0 1 0 1Чтобы использовать битовые карты, база данных должна поддерживать операции с битовыми строками. Это может быть либо встроенный функционал, либо быть реализован с помощью какого-либо модуля расширения. В примере будем использовать функции $bit из состава Cache или MiniM.
Операции получения идентификаторов строк по значениям атрибутов сводятся к использованию битовых операций с битовыми картами и выборке из получившейся битовой карты позиций ненулевых битов. Значения этих позиций считаются идентификаторами строк.
К особенностям битовых индексов относится то, что они могут быть, как и простые индексы, составными, но не могут быть кластерными. Другим ограничением является то, что идентификатором строки данных должно быть строго натуральное число. В большинстве систем второе ограничение совершенно незаметно, поскольку идентификаторы и без того поддерживаются в автоинкрементном режиме.
Битовые индексы и простые индексы по одной и той же таблице могут быть совмещены. Но если для таблицы используется кластерный индекс, то битовый индекс для нее уже не может быть применен, поскольку идентификатор строки фактически нечисловой. Совмещение и одновременное применение простых и битовых индексов выполняется алгоритмически. Также может быть организована многоиндексная выборка совместно из нескольких простых и битовых индексов.
Небольшой пример реализации битового индекса:
ind04 ; битовые индексы, автоматическое поддержание идентификатора
q
CreateRecords()
k ^Index
k ^Data
n i,Figures,Colors,Counts,Figure,Color,Count,id
s Figures="квадрат~круг~отрезок~треугольник"
s Colors="красный~зелёный~синий~белый"
s Counts="2~5~12~8"
f i=1:1:12 d
. s Figure=$p(Figures,"~",$r(4)+1)
. s Color=$p(Colors,"~",$r(4)+1)
. s Count=$p(Counts,"~",$r(4)+1)
. s id=$$InsertRecord(Figure_"~"_Color_"~"_Count)
q
InsertRecord(RecordValues)
n id s id=$i(^Data)
l +^Data(id)
s ^Data(id)=RecordValues
d InsertIndexRecords(id,RecordValues)
l -^Data(id)
q id
DeleteRecord(id)
q:'$d(^Data(id))
l +^Data(id)
n RecordValues s RecordValues=$g(^Data(id))
d DeleteIndexRecords(id,RecordValues)
k ^Data(id)
l -^Data(id)
q
UpdateRecord(id,RecordValues)
q:'$d(^Data(id))
l +^Data(id)
n OldRecordValues s OldRecordValues=$g(^Data(id))
d DeleteIndexRecords(id,OldRecordValues)
s ^Data(id)=RecordValues
d InsertIndexRecords(id,RecordValues)
l -^Data(id)
q
DeleteIndex(IndexName)
k ^Index(IndexName)
q
InsertIndexRecords(id,RecordValues)
d InsertIndexRecord("Figure",id,$p((RecordValues),"~",1))
d InsertIndexRecord("Color",id,$p((RecordValues),"~",2))
d InsertIndexRecord("Count",id,$p((RecordValues),"~",3))
q
DeleteIndexRecords(id,RecordValues)
d DeleteIndexRecord("Figure",id,$p((RecordValues),"~",1))
d DeleteIndexRecord("Color",id,$p((RecordValues),"~",2))
d DeleteIndexRecord("Count",id,$p((RecordValues),"~",3))
q
InsertIndexRecord(IndexName,id,Value)
s $bit(^Index(IndexName,Value),id)=1
q
DeleteIndexRecord(IndexName,id,Value)
s $bit(^Index(IndexName,Value),id)=0
q
Сравнив с рутиной ind01 для простых индексов, несложно понять, что единственные
отличия содержатся в функциях InsertIndexRecord и DeleteIndexRecord. Это простой
учебный пример, здесь не проверяется что идентификатор действительно является
натуральным числом.
Также строится только одна битовая карта. В реальном приложении, несмотря на то, что хранится только один бит на запись, битовые карты должны быть сегментированы, поскольку работа с неограниченными строками обычно не предусматривается. Разбиение по сегментам выполняется вычислением номера сегмента и позиции в сегменте по значению идентификатора. В системе должна быть выбрана одна и та же гранулярность сегмента, чтобы битовые логические операции выполнялись корректно. Точное значение размера битового сегмента, вообще говоря, лучше определять экспериментально. Об этом пойдет речь в части сравнения битовых и простых индексов.
Простой пример сегментирования битового индекса:
#define BITSEGMENT 32000 InsertIndexRecord(IndexName,id,Value) n seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT s $bit(^Index(IndexName,Value,seg),pos)=1 q DeleteIndexRecord(IndexName,id,Value) n seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT s $bit(^Index(IndexName,Value,seg),pos)=0 qЗдесь номер сегмента получается делением идентификатора нацело на размер сегмента, а позиция в сегменте определяется остатком от деления нацело идентификатора на размер сегмента. Здесь, поскольку значения идентификаторов рассматриваются как позиции битов, величина сегмента BITSEGMENT означает число бит, а не байт. В зависимости от применяемой версии сервера, размера блока базы данных и метода применяемой упаковки битовой карты эту величину можно подобрать экспериментально более оптимальной, или обратиться в техподдержку MUMPS системы за рекомендациями.
В действительности, это тоже еще не все - у реализации битовых функций в Cach'e и MiniM есть техническая особенность - нельзя использовать нулевое число в качестве позиции в сегменте (третий параметр). При этом число ноль получается для идентификаторов, кратных размеру сегмента. Чтобы избежать этой проблемы, можно поступить просто - после вычисления правильной позиции в сегменте к ней прибавить единицу, например, и во всех функциях, использующих сегменты, учитывать эту неправильную единицу. Например:
#define BITSEGMENT 32000 InsertIndexRecord(IndexName,id,Value) n seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT+1 s $bit(^Index(IndexName,Value,seg),pos)=1 q DeleteIndexRecord(IndexName,id,Value) n seg,pos s seg=id\$$$BITSEGMENT s pos=id#$$$BITSEGMENT+1 s $bit(^Index(IndexName,Value,seg),pos)=0 qК обычным достоинствам битовых индексов относится то, что битовые операции могут быть оптимизированы и могут выполняться значительно быстрее, чем операции с простыми списками. Другим достоинством является относительно меньший объем используемой дисковой памяти, чем в случае обычных индексов.
К недостаткам битовых индексов относятся необходимость применения битовых операций к всей битовой карте независимо от того, сколько реально там содержится значимых бит. Поскольку в большинстве случаев процессы обращаются к объектам в относительно небольшом диапазоне идентификаторов, вероятность что эти идентификаторы находятся в одном сегменте увеличивается. В случае же уменьшения величины сегмента битовый индекс по структуре и характеристикам приближается к простому обратному списку. В ситуации "размер сегмента равен единице" битовый индекс полностью вырождается в обычный.
К как преимуществам, так и недостаткам битовых индексов, в зависимости от характера их применения может быть отнесено сочетание их реализации с транзакционностью прикладной системы. Для отдельных реализаций битовых индексов транзакционность системы будет негативным фактором, для других она не имеет значения. Более подробной этот вопрос описывается в главе о транзакциях.
В любом случае выбор вида индекса оставим за программистом и руководителем проекта. Отметим, что сейчас мы занимаемся только техническими вопросами, на основе которых и можно сделать аргументированный выбор. В документации и рекомендациях фирм - производителей движков баз данных также можно найти советы по выбору применяемых индексов. Важно понимать, на основе чего они сделаны, каковы характеристики движков этих баз данных и для каких характерных операций этот выбор предлагается.
Подробнее о книге "MUMPS СУБД"
Комментариев нет:
Отправить комментарий