3. Suchen in Bayer-Bäumen

1. Durchsuchen eines Knotens nach dem zu suchenden Element
2. Die Auswahl des richtigen Unterbaumes in dem die Suche fortgesetzt wird, wenn unter I. das Element nicht gefunden wurde

1. Element ist im Knoten enthalten.
2. Element ist nicht im Knoten enthalten.
   Wenn Element > "Element von Knoten an Position X" und
   Element < "Element von Knoten an Position X+1" dann wird
   die Suche beim Unterbaum von "Element von Knoten X" fortgesetzt.

• erste Page durchsuchen:
  
  

  12

  
  Element nicht gefunden!
• nächste Page durchsuchen:
  
  

  18

  24

  
  Element nicht gefunden!
• nächste Page durchsuchen:
  
  

  19

  20

  22

  23

  
  Element an Position 2 gefunden!

Function SucheInPage(Var Page: PPage; Element: TElement; Var Pos: Integer): Boolean;

Var
    I,low,high: Integer;
    gefunden: Boolean;

Begin
     low:=0;
     high:=Page^.Anzahl+1;
     gefunden:=False;
     While (low+1<high) and (not gefunden) do
     Begin
          I:=(low+high) Div 2;
          If Element.Key=Page^.Elemente[I].Key Then
           gefunden:=True;
          If Element.Key<Page^.Elemente[I].Key Then
           high:=I
          If Element.Key>Page^.Elemente[I].Key Then
           low:=I;
     End;
     If not gefunden Then
      Pos:=low
     Else
      Pos:=I;
     SucheInPage:=gefunden;
End;

Function Search(Element: TElement): PPage;

 Function Retrieve(PageLink: Longint): PPage;

 Begin
      Implementierung
 End;

Begin
      Search:=Retrieve(Rootlink); { Baum durchsuchen }
End;

Function Retrieve(PageLink: Longint): PPage;

Var
    Page: PPage;
    Pos,I: Integer;

Begin
     { letzter Knoten erreicht (unterstes Baum-Level) }
     If PageLink=Null Then
      Retrieve:=Nil
     Else
     Begin
          { Page einlesen }
          Page:=LoadPage(PageLink);
          { Element in Page suchen }
          If SucheInPage(Page,Element,Pos) Then
           Retrieve:=Page
          Else
          Begin
               PageLink:=Page^.Elemente[Pos].Link;
               Dispose(Page);
               { nächste Page durchsuchen }
	       Page:=Retrieve(PageLink);
	       Retrieve:=Page;
          End;
     End;
End;