H-Baum

Die ersten zehn Stufen eines H-Baumes

Als H-Baum wird ein spezieller Baum in der Graphentheorie bezeichnet. Es handelt sich dabei um die Einbettung eines binären Baums in ein rechteckiges Gitter – Wurzel in der Mitte –, sodass Baum und Teilbäume die Form des Großbuchstabens H zeigen. Jeder Knoten kann wieder Mittelpunkt eines Hs sein.

Der H-Baum ist eine FASS-Kurve, d. h. er füllt die ganze Ebene aus. Seine fraktale Hausdorff-Dimension ist 2. Mit jeder neuen Iteration multipliziert sich die Gesamtlänge der Kurve um $\sqrt 2$.

H-Bäume spielen beim Entwurf von digitalen Schaltungen wie Very Large Scale Integration (VLSI) oder Field Programmable Gate Array (FPGAs) zur Signalverteilung eine Rolle. So wird in jenen Schaltungen über H-Bäume die Übertragung der zentral eingespeisten Taktsignale zu allen Schaltungsteilen am Chip mit identischen Übertragungszeiten sichergestellt.

Im Dateisystem ext3 für Linux sowie dessen Nachfolger ext4 werden H-Bäume für die Verzeichnis-Indizes verwendet.

Ein anderes Beispiel für die Verwendung von H-Bäumen ist die Abbildung der Kommunikationsstruktur eines Programms auf die Prozessoren in einem Computercluster.

Weblinks

• H-Fractal in Wolfram Demonstration Projekt
• Famous Fractals: H-Fractal