Algorithmen
Btree
Hier versuche ich einen B*-Baum mit RAMS zu bauen. Betriebssystemmaßig steckt eine speicherabbgebildete Datei dahinter.
Zum Algorithmus
Der Witz an B-Bäumen ist, daß sie an der Wurzel wachsen, und nicht an den Blättern. Dadurch wird die Balancierung erreicht.
- B-tree
-
Balancierter Baum, in dem jeder Knoten zwischen t-1 und 2t-1 Kinder hat.
- Eignet sich hervorragend für langsamen Speicher. Ein Knoten kann in schnellen Cache/Hauptpeicher gehalten werden und daher schnell durchsucht werden.
Wenn viele Schlüssel in der Seite Platz haben (t groß),
ist die tiefe gering.
- B+-Tree
- Ein B-Baum, in dem die Schüssel in den Knoten gespeichert werden, die
eigentlichen Sätze in den Blättern.
- B*-tree
- B-Baum, bei dem die Knoten nur zu 2/3 voll gehalten werden
Bei Donald E. Knuth: B-Trees werden in Band III, "Sorting
And Searching" von The Art Of Computer Programming in Sektion 6.2.4,
"Multiway Trees" naeher besprochen. (Hinweis von A.Kübler)
Bemerkungen
- Gemäß der Implementierungsidee bei RAMS unterscheiden wir zwischen dem Layout des Persistenzzustands und den transienten Zugriffsklassen.
- Die direkten Zugriffsklassen für die Blattknoten (LeavePageAcess)
und der Indexknoten (IndexPageAccess) sind Ableitungen eines
RAMS::Mseg und Technologieunabhängig. (z.B. kann über die Read/Write oder die Mmap-Schnittstelle auf die Datei auf der Platte zugegriffen werden.
- Es gibt eine Strategieklasse zur Steuerung der Teilung der Seiten.
Testprogramm
- btree
- siehe Aufruffehlermeldung
Ach ja ...
Weitere Links zu Implementierungen
- BTree-Implementation in C++
- aber nicht parallelisiert
- gxvtree
- beschreibt eine B-Baum-Implementierung
aber ConncurrentBtreeOperations beim Insert wird auch der ganze Baum geloggt.
(LizenzLGPL fuer commercial usw. )
- The Design of the Infinity Data Base Engine B-Tree
- in java, beschreibt oberflächlich verschiedene Locking-Strategien
- Laut cl.cam.ac.uk hat die SPECjBB-Benchmark auch eine Btree-Implementierung
Informatik- und Netzwerkverein Ravensburg e.V
Rudolf Weber