Was ist der X-Baum?
Der X-Baum ist ein hybrider Baum, der mit hohen Dimensionen umgehen können soll. Die Idee ist, dass bei starker Überlappung ein sequentieller Durchlauf schneller ist als ein Baum. Dann werden Superknoten eingefügt, die beliebig viele DB-Seiten umfassen können und sequentiell durchsucht werden.
Tags: baum, mehrdimensional, x-baum
Source: MMDB 2009 Kapitel 7
Source: MMDB 2009 Kapitel 7
Was passiert beim X-Baum beim Knotenüberlauf?
Jeder MBR verwaltet eine Split-Historie, die alle bereits verwendeten Zerlegungsdimensionen speichert.
Beim Überlauf wird nun
1. zuerst eine herkömmliche topologische Zerlegung gemacht.
2. wird ein vordefinierter Überlappungsgrad überschritten, so wird unter Ausnutzung der Split-Historie eine Zerlegungsdimension ausgesucht.
3. wird dadurch die Balance-Bedingung verletzt (Mindestfüllgrad), wird ein Superknoten erzeugt.
Ab etwa 15 Dimensionen wird der X-Baum zu einem einzigen Superknoten.
Beim Überlauf wird nun
1. zuerst eine herkömmliche topologische Zerlegung gemacht.
2. wird ein vordefinierter Überlappungsgrad überschritten, so wird unter Ausnutzung der Split-Historie eine Zerlegungsdimension ausgesucht.
3. wird dadurch die Balance-Bedingung verletzt (Mindestfüllgrad), wird ein Superknoten erzeugt.
Ab etwa 15 Dimensionen wird der X-Baum zu einem einzigen Superknoten.
Tags: baum, mehrdimensional, x-baum
Source: MMDB 2009 Kapitel 7
Source: MMDB 2009 Kapitel 7
Flashcard set info:
Author: kread
Main topic: Informatik
Topic: Semantic Web
School / Univ.: Universität Koblenz-Landau
City: Koblenz
Published: 22.10.2010
Card tags:
All cards (35)
baum (9)
eigenschaften (1)
hs (1)
indexstruktur (1)
m-baum (2)
mehrdimensional (10)
modelle (1)
objektrelational (1)
oodbms (1)
probleme (1)
r-baum (3)
x-baum (2)
