Zum Inhalt springen

UB-Baum

aus Wikipedia, der freien Enzyklopädie

Der UB-Baum („Universal B-Tree“) wurde von Rudolf Bayer und Volker Markl vorgeschlagen und ist eine Datenstruktur für mehrdimensionale Datenbanksysteme. Es ist ein B+-Baum, bei dem die Daten nach der Z-Kurve (Berechnen der Z-Werte durch bitweise Verschränkung der Schlüssel) sortiert abgelegt werden. Die Kernidee dieses Verfahrens wurde schon sehr viel früher (für Suchbäume im Allgemeinen von Tropf und Herzog<ref name="tropf">H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77. (PDF; 1,5 MB)</ref> sowie für B-Bäume von Orenstein und Merrett<ref>J. A. Orenstein and T. H. Merrett. A Class of Data Structures for Associative Searching. In PODS, 1984.</ref>) vorgeschlagen.

Einfügen, Löschen und exakte Anfragen werden behandelt wie bei normalen B+ Bäumen. Für mehrdimensionale Bereichsanfragen benötigt man ein Verfahren, um, ausgehend von einem in der Datenstruktur angetroffenen Z-Wert, den nächsten zu finden, der innerhalb des mehrdimensionalen Suchbereichs liegt.

Das hierfür ursprünglich von Rudolf Bayer angegebene Verfahren war im Aufwand exponentiell mit der Anzahl der Dimensionen und somit für mehr als 4 Dimensionen nicht praktisch verwendbar.<ref><templatestyles src="Webarchiv/styles.css" />{{#if:20160304044305 

      | {{#ifeq: 20160304044305 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. | {{#invoke:WLink|getEscapedTitle|V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20160304044305}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. | {{#invoke:WLink|getEscapedTitle|V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20160304044305}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. | {{#invoke:WLink|getEscapedTitle|V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. | {{#invoke:WLink|getEscapedTitle|V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. | {{#invoke:WLink|getEscapedTitle|V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999. | {{#invoke:WLink|getEscapedTitle|V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20160304044305|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf}}
    || {{#if:  || }}
  }}{{#if: V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.
    | {{#if: {{#invoke:WLink|isBracketedLink|V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/Mar99.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} (PDF; 1,4 MB)</ref> Eine Lösung für das Problem („crucial part of the UB-tree range query“), wurde später beschrieben<ref><templatestyles src="Webarchiv/styles.css" />{{#if:20160304060154
      | {{#ifeq: 20160304060154 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272. | {{#invoke:WLink|getEscapedTitle|F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20160304060154}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272. | {{#invoke:WLink|getEscapedTitle|F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20160304060154}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272. | {{#invoke:WLink|getEscapedTitle|F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272. | {{#invoke:WLink|getEscapedTitle|F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272. | {{#invoke:WLink|getEscapedTitle|F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272. | {{#invoke:WLink|getEscapedTitle|F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.}} | {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20160304060154|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf}}
    || {{#if:  || }}
  }}{{#if: F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.
    | {{#if: {{#invoke:WLink|isBracketedLink|F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Large Databases, (VLDB) 2000, pp. 263–272.}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://mistral.informatik.tu-muenchen.de/results/publications/RMF+00.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} (PDF; 136 kB)</ref>. Eine Lösung war bereits viel früher beschrieben worden in<ref name="tropf"/> („BIGMIN/LITMAX“-Berechnung).

Siehe auch

Einzelnachweise

<references />

Abgerufen von „https://wiki-de.moshellshocker.dns64.de/index.php?title=UB-Baum&oldid=723198“