Двоичные деревья и B-деревья

Задача поиска данных в большом массиве (или файле) возникает очень часто (во всех приложениях, работающих с базами данных, но не только в них). Если массив упорядочен, можно использовать метод деления отрезка пополам. Для этого нужно приблизительно Log(N) сравнений - совсем немного. Но если тебуется вставлять новые данные и удалять имеющиеся, затраты на поддержание порядка могут быть непомерны - в худшем случае для вставки и для удаления потребуется N операций. Если не поддерживать порядок данных - непомерны будут затраты на поиск. Кроме того, для разных целей может быть нужен разный порядок данных, а физический порядок всего один. Решение состоит в поддержке индексов - дополнительных упорядоченных структур данных, содержащих ключи и ссылки на основные данные. Порядок самих данных при этом не играет никакой роли. Индексный поиск может быть столь же эффективен, как и поиск методом деления деления в упорядоченном массиве, плюс к этому вставки и удаления также могут выполняться быстро. Существует несколько способов построения индексов. Во-первых, это так называемые B-деревья. В определенном смысле B-дерево - обобщение двоичного дерева - простой конструкции, не обладающей, однако, гарантированной эффективностью. B-дерево - не единственнная эффективная конструкция индекса. Можно упомянуть красно-черные деревья - еще одно усовершенствование двоичных деревьев (в настоящее время у меня нет соответствующего примера).

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

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

define nNODE 8192 struct TNode int pData; int pLeft; int pRight; section int pFree; end TNode Node[nNODE]; int pRoot; int pFree; void Stop(char @S); void Init() pRoot=-1; pFree=-1; int P= 0; while P<nNODE do Node[P].pFree=pFree; pFree=P; inc P; end end int Comp(int P1, P2) // функция сравнения ключей select case P1<P2: return -1; case P1>P2: return 1; end return 0; end void Insert(int pData) int @P=@pRoot; while P>=0 do int C=Comp(Node[P].pData,pData); select case C>0: @P=@Node[P].pLeft; case C<0: @P=@Node[P].pRight; default: return // Повтор ключа end end if pFree<0 then Stop("Недостаточно свободных узлов"); end P =pFree; pFree = Node[pFree].pFree; Node[P].pData =pData; Node[P].pLeft =-1; Node[P].pRight=-1; end void Delete(int pData) int @P=@pRoot; while TRUE do if P<0 then return // Ключ не найден end int C=Comp(Node[P].pData,pData); select case C>0: @P=@Node[P].pLeft; case C<0: @P=@Node[P].pRight; default: exit end end int P2=P; if Node[P2].pLeft<0 then P=Node[P2].pRight; Node [P2].pFree=pFree; pFree= P2; return end if Node[P2].pRight<0 then P=Node[P2].pLeft; Node [P2].pFree=pFree; pFree=P2; return end int @P1=@Node[P2].pLeft; while Node[P1].pRight>=0 do @P1=@Node[P1].pRight; end Node[P].pData=Node[P1].pData; int P0=P1; P1=Node[P1].pLeft; Node [P0].pFree=pFree; pFree = P0; end Изменение ключа реализуется посредством удаления старого и вставки нового. Двоичное дерево имеет существенный недостаток - в худшем случае (например, при вставке упорядоченнной последовательности ключей) оно вырождается в список. Этот недостаток может быть устранен, ести предусмотреть в узле место для двух ключей и трех ссылок (в общем случае N ключей и (N+1) ссылки) и усложнить функции вставки/удаления. Новый ключ всегда добавляется в нижнюю страницу, если страница переполняется, она делится на две и средний ключ переносится на вышележащую страницу. Если и эта страница переполняется, она тоже делится на две. В худшем случае корневая страница будет поделена на две и будет создан новый корень, содержащий единственный ключ. Высота дерева при этом увеличится на единицу. При удалении наоборот, если страница становится заполненной менее чем наполовину, она либо дополняется ключом из соседней страницы, либо две страницы объединяются (при этом один ключ берется из вышележащей страницы): define nDATA 8 // >=2 define nDATA1 9 // nDATA+1 define nPAGE 2048 define nLINK 512 define nPATH 32 struct TPage int pData[nDATA]; int pLink; int nData; section int pPage; end struct TLink int pPage[nDATA1]; section int pLink; end struct TPath int pPage; int pData; end TPage Page[nPAGE]; TLink Link[nLINK]; int pPage; // Указатель на список свободных стpаниц данных int pLink; // Указатель на список свободных стpаниц ссылок int pRoot; // Указатель на коpневую стpаницу деpева void Stop(char @S); void Init() pPage=-1; int P= 0; while P<nPAGE do Page[P].pPage=pPage; pPage=P; inc P; end pLink=-1; int L= 0; while L<nLINK do Link[L].pLink=pLink; pLink=L; inc L; end pRoot=-1; end int Comp(int P1, P2) // функция сравнения ключей select case P1<P2: return -1; case P1>P2: return 1; end return 0; end void Insert(int pData) TPath Path[nPATH]; int N; int P; P=pRoot; N=0; while P>=0 do if N>=nPATH then Stop("Высота деpева слишком велика"); end int I=0; int J=Page[P].nData; while I<J do int K=(I+J)/2; int S=Comp(Page[P].pData[K],pData); select case S>0: J=K; case S<0: I=K+1; default: return // Повтоp ключа end end Path[N].pPage=P; Path[N].pData=I; inc N; int L=Page[P].pLink; if L<0 then exit end P=Link[L].pPage[I]; end int P0=-1; int P1=-1; while TRUE do dec N; if N<0 then if pPage<0 then Stop("Недостаточно стpаниц данных"); end pRoot=pPage; pPage=Page[pPage].pPage; Page[pRoot].pData[0]= pData; Page[pRoot].pLink =-1; Page[pRoot].nData = 1; if P0<0 then exit end if pLink<0 then Stop("Недостаточно стpаниц ссылок"); end int L=pLink; pLink=Link[pLink].pLink; Link[L].pPage[0]=P0; Link[L].pPage[1]=P1; Page[pRoot].pLink=L; exit end P=Path[N].pPage; if Page[P].nData<nDATA then int I=Page[P].nData; while I>Path[N].pData do Page[P].pData[I]=Page[P].pData[I-1]; dec I; end Page[P].pData[I]=pData; inc Page[P].nData; if P0<0 then exit end int L=Page[P].pLink; int J=Page[P].nData; // Новое значение while J>Path[N].pData do Link[L].pPage[J]=Link[L].pPage[J-1]; dec J; end Link[L].pPage[J] =P0; Link[L].pPage[J+1]=P1; exit end if pPage<0 then Stop("Недостаточно стpаниц данных"); end int P2=pPage; pPage =Page[pPage].pPage; int L, L2=-1; if P0>=0 then if pLink<0 then Stop("Недостаточно стpаниц ссылок"); end L =Page[P].pLink; L2 =pLink; pLink=Link[pLink].pLink; end Page[P2].pLink=L2; int M=nDATA/2; if Path[N].pData<=M then int I=M; int J=0; while I<nDATA do Page[P2].pData[J]=Page[P].pData[I]; inc J; inc I; end Page[P2].nData=J; I=M; while I>Path[N].pData do Page[P].pData[I]=Page[P].pData[I-1]; dec I; end Page[P].pData[I]=pData; if L2>=0 then I=M+1; J=1; while I<=nDATA do Link[L2].pPage[J]=Link[L].pPage[I]; inc J; inc I; end I=M+1; while I>Path[N].pData do Link[L].pPage[I]=Link[L].pPage[I-1]; dec I; end Link[L].pPage[I] =P0; Link[L].pPage[I+1]=P1; Link[L2].pPage[0]=Link[L].pPage[M+1]; end else int I=M+1; int J=0; while I<Path[N].pData do Page[P2].pData[J]=Page[P].pData[I]; inc J; inc I; end Page[P2].pData[J]=pData; inc J; while I<nDATA do Page[P2].pData[J]=Page[P].pData[I]; inc J; inc I; end Page[P2].nData=J; if L2>=0 then I=M+1; J=0; while I<Path[N].pData do Link[L2].pPage[J]=Link[L].pPage[I]; inc J; inc I; end Link[L2].pPage[J]=P0; inc J; Link[L2].pPage[J]=P1; inc J; inc I; while I<=nDATA do Link[L2].pPage[J]=Link[L].pPage[I]; inc J; inc I; end end end Page[P].nData=M; pData=Page[P].pData[M]; P0 =P; P1 =P2; end end void Delete(int pData) TPath Path[nPATH]; int N; int P; P=pRoot; N=0; while TRUE do if N>=nPATH then Stop("Высота деpева слишком велика"); end int S=1; int I=0; int J=Page[P].nData; while I<J do int K=(I+J)/2; S=Comp(Page[P].pData[K],pData); select case S>0: J=K; case S<0: I=K+1; default: I=K; exit end end Path[N].pPage=P; Path[N].pData=I; inc N; if S=0 then if Page[P].pLink>=0 then int P1=Link[Page[P].pLink].pPage[I]; while TRUE do if N>=nPATH then Stop("Высота деpева слишком велика"); end Path[N].pPage=P1; Path[N].pData=Page[P1].nData; inc N; if Page[P1].pLink<0 then exit end P1=Link[Page[P1].pLink].pPage[Page[P1].nData]; end dec Page[P1].nData; Page[P].pData[I]=Page[P1].pData[Page[P1].nData]; else while I+1<Page[P].nData do Page[P].pData[I]=Page[P].pData[I+1]; inc I; end dec Page[P].nData; end exit end if Page[P].pLink<0 then return // Ключ не найден end P=Link[Page[P].pLink].pPage[I]; end while N>1 do dec N; if Page[Path[N].pPage].nData>=nDATA/2 then return end int P0; int P1; int M; int S; P=Path[N-1].pPage; M=Path[N-1].pData; S=M; if M<Page[P].nData then P0=Path[N].pPage; P1=Link[Page[P].pLink].pPage[M+1]; else P0=Link[Page[P].pLink].pPage[M-1]; P1=Path[N].pPage; dec M; end int L0=Page[P0].pLink; int L1=Page[P1].pLink; if Page[P0].nData+Page[P1].nData+1>nDATA then if S=M then // Стpаница P0 недостаточно заполнена Page[P0].pData[Page[P0].nData]=Page[P] .pData[M]; Page[P] .pData[M] =Page[P1].pData[0]; int I=0; while I+1<Page[P1].nData do Page[P1].pData[I]=Page[P1].pData[I+1]; inc I; end if L0>=0 then Link[L0].pPage[Page[P0].nData+1]=Link[L1].pPage[0]; I=0; while I+1<=Page[P1].nData do Link[L1].pPage[I]=Link[L1].pPage[I+1]; inc I; end end inc Page[P0].nData; dec Page[P1].nData; else // Стpаница P1 недостаточно заполнена int I=Page[P1].nData; while I>0 do Page[P1].pData[I]=Page[P1].pData[I-1]; dec I; end Page[P1].pData[0]=Page[P] .pData[M]; Page[P] .pData[M]=Page[P0].pData[Page[P0].nData-1]; if L0>=0 then I=Page[P1].nData+1; while I>0 do Link[L1].pPage[I]=Link[L1].pPage[I-1]; dec I; end Link[L1].pPage[0]=Link[L0].pPage[Page[P0].nData]; end dec Page[P0].nData; inc Page[P1].nData; end return end // слияние стpаниц int I=Page[P0].nData; int K=I; Page[P0].pData[I]=Page[P].pData[M]; inc I; int J=0; while J<Page[P1].nData do Page[P0].pData[I]=Page[P1].pData[J]; inc I; inc J; end Page[P0].nData=I; if L0>=0 then I=K+1; J=0; while J<=Page[P1].nData do Link[L0].pPage[I]=Link[L1].pPage[J]; inc I; inc J; end Link[L1].pLink=pLink; pLink =L1; end Page[P1].pPage=pPage; pPage =P1; I=M; while I+1<Page[P].nData do Page[P].pData[I]=Page[P].pData[I+1]; inc I; end int L=Page[P].pLink; I=M+1; while I+1<=Page[P].nData do Link[L].pPage[I]=Link[L].pPage[I+1]; inc I; end dec Page[P].nData; end if Page[pRoot].nData>0 then return end int L=Page[pRoot].pLink; if L>=0 then Page[pRoot].pPage=pPage; pPage=pRoot; pRoot=Link[L].pPage[0]; Link[L].pLink=pLink; pLink =L; return end Page[pRoot].pPage=pPage; pPage =pRoot; pRoot =-1; end Эти процедуры гарантируют, что все страницы дерева (кроме корневой) будут заполнены не менее чем на половину. В силу этого высота дерева (и затраты времени на вставку, удаление и поиск) никогда не будут большими. Сам поиск значительно проще вставки и удаления. Поиск единственного ключа очень прост, с него начинается функция Delete и повторять этот фрагмент еще раз нет смысла, поиск ключей из заданного диапазона немного сложнее, но все равно он значительно проще вставки/удаления:

void search(int P; int Max) int I=0; while I<Page[P].nData do if Page[P].pLink>=0 then search(Link[Page[P].pLink].pPage[I],Max); end if Comp(Page[P].pData[I],Max)>0 then return end puts(@Str(Page[P].pData[I])); putc(#13); putc(#10); inc I; end if Page[P].pLink>=0 then search(Link[Page[P].pLink].pPage[I],Max); end end void Select(int P; int Min, Max) if P<0 then return end int I=0; int J=Page[P].nData; while I<J do int K=(I+J)/2; if Comp(Page[P].pData[K],Min)>=0 then J=K; else I=K+1; end end if Page[P].pLink>=0 then Select(Link[Page[P].pLink].pPage[I],Min,Max); end while I<Page[P].nData do if Comp(Page[P].pData[I],Max)>0 then return end puts(@Str(Page[P].pData[I])); putc(#13); putc(#10); if Page[P].pLink>=0 then search(Link[Page[P].pLink].pPage[I+1],Max); end inc I; end end

Функция Select печатает все ключи, находящиеся в диапазоне от Min до Max.

B-дерево легко адаптируеся для случая, когда данные размещаются на дисках. Для этого нужно хранить ключи, ссылки на данные и ссылки на страницы индекса вместе (в приведенном примере ключи доступны по ссылкам на данные, а ссылки на страницы хранятся отдельно от ссылок на данные для экономии памяти - большинство страниц не содержат ссылок на другие страницы). Размер страницы должен выбираться не слишком малым.

Эффективность B-деревьев возрастает с увеличением размера массива данных. Из-за этого пример B-дерева в памяти размером 64K не очень показателен. Например, если использовать его для поиска в таблице меток ассемблера asm8086, выигрыш по ставнению с простым перебором при компиляции context.asm (около двух тысяч меток) будет примерно пятикратным. Это несколько хуже, чем поиск методом половинного деления, но зато B-дерево [почти] не зависит от порядка меток.



Сайт создан в системе uCoz