MUMPS: Индекс поиска по фрагменту

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

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

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

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

USER>s Value="green blue"

USER>f i=1:1:len w $e(Value,i,len),!
green blue
reen blue
een blue
en blue
n blue
 blue
blue
lue
ue
e

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

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
InsertIndexRecords(id,RecordValues)
 d InsertIndexRecord("Figure",id,$p((RecordValues),"~",1))
 d InsertIndexRecord("Color",id,$p((RecordValues),"~",2))
 q
DeleteIndexRecords(id,RecordValues)
 d DeleteIndexRecord("Figure",id,$p((RecordValues),"~",1))
 d DeleteIndexRecord("Color",id,$p((RecordValues),"~",2))
 q
InsertIndexRecord(IndexName,id,Value)
 n i,len s len=$l(Value)
 f i=1:1:len s ^Index(IndexName,$e(Value,i,len),id)=""
 q
DeleteIndexRecord(IndexName,id,Value)
 n i,len s len=$l(Value)
 f i=1:1:len k ^Index(IndexName,$e(Value,i,len),id)
 q
FindFigure(part,ids)
 n ref,id
 s ref=$na(^Index("Figure",part)) 
 f  s ref=$q(@ref) q:(ref="")!($qs(ref,2)'[part)  d
 . s id=$qs(ref,3)
 . s ids(id)=""
 q

Здесь функция FindFigure выдает в подиндексы переменной ids найденные идентификаторы, например

  d FindFigure^indpart("тре",.ids)

находит объекты, у которых атрибут Figure имеет значение "отрезок" и "треугольник".

В действительности иногда приходитcя искать по гораздо более сложному условию, в котором используется не один фрагмент, а несколько, и накладывается условие на взаимное расположение найденных фрагментов, на расстояние между фрагментами в значении. В этом случае требуется внимательное составление правила получения фрагментов по значению атрибутов, чтобы учесть все предъявляемые требования. В SQL - ориентированных базах данных есть выражение для условия поиска LIKE. Приведенная техника индекса поиска по фрагменту примерно соотносится именно с таким условием поиска. Но условие LIKE, конечно, имеет гораздо большую сложность.

Подробнее о книге "MUMPS СУБД"