Intervall-Indexstrukturen in Datenbanksystemen

Inhaltsverzeichnis

• 1. Einleitung.
• 2. Grundlagen.
• 2.1. Das Points-in-Regions Mengenproblem.
• 2.2 Zugrundeliegendes Speicher- und Berechnungsmodell.
• 2.3. Der Priority Search Tree.
• 2.4. Der Segment Tree.
• 2.5. Der Interval Tree.
• 3. Interne und externe Lösungen des Points-in-Regions Mengenproblems.
• 3.1. Interne Lösungen.
• 3.2. Interne Lösungen mit sublinearem Speicherplatzbedarf.
• 3.3. Externe Lösungen.
• 3.4. Vergleich von Plane-Sweep und Divide-And-Conquer.
• 4. Der XP-Baum.
• 4.1. Struktur.
• 4.2. Suchen.
• 4.3. Einfügen.
• 4.4. Löschen.
• 4.5. Aufbau einer balancierten Struktur.
• 4.6. Mehrstufige XP-Bäume.
• 4.7. Spezialfall: Verwaltung von Intervallen.
• 4.8. Experimentelle Untersuchungen.
• 5. Der EST.
• 5.1. Struktur.
• 5.2. Suchen.
• 5.3. Einfügen.
• 5.4. Löschen.
• 5.5. Speicherplatzbedarf.
• 5.6. Das Cover-Balancing Problem.
• 5.7. Analytische Betrachtungen.
• 5.8. Spezialfall: Verwaltung eindimensionaler Punkte.
• 6. Der EIT.
• 6.1. Struktur.
• 6.2. Suchen.
• 6.3. Einfügen.
• 6.4. Löschen.
• 6.5. Speicherplatzbedarf.
• 6.6. Analytische Betrachtungen für gleichmäßig verteilte Intervalle fester Länge.
• 6.7. Spezialfall: Verwaltung eindimensionaler Punkte.
• 6.8. Ein modifizierter interner Interval Tree.
• 7. Vergleich von XP-Baum, EST und EIT.
• 8. Indexstrukturen für ausgedehnte geometrische Objekte.
• 9. Zusammenfassung und abschließende Bemerkungen.
• Anhang I: Grundlegende Suchen auf Intervallen mit dem XP-Baum.
• Anhang II: Grundlegende Suchen auf Intervallen mit dem EU.