UB-tree (original) (raw)
Der UB-Baum („Universal B-Tree“) wurde von Rudolf Bayer und vorgeschlagen und isteine 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 sowie für B-Bäume von Orenstein und Merrett) vorgeschlagen.
| Property | Value |
|---|---|
| dbo:abstract | Der UB-Baum („Universal B-Tree“) wurde von Rudolf Bayer und vorgeschlagen und isteine 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 sowie für B-Bäume von Orenstein und Merrett) 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. Eine Lösung für das Problem („crucial part of the UB-tree range query“), linear mit der Bitlänge der Z-Werte, wurde später beschrieben („GetNextZ-address“); diese Methode war bereits beschrieben worden in („BIGMIN“-Berechnung). (de) The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys. Insertion, deletion, and point query are done as with ordinary B+ trees. To perform range searches in multidimensional point data, however, an algorithm must be provided for calculating, from a point encountered in the data base, the next Z-value which is in the multidimensional search range. The original algorithm to solve this key problem was exponential with the dimensionality and thus not feasible ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" linear with the z-address bit length has been described later. This method has already been described in an older paper where using Z-order with search trees has first been proposed. (en) UB-дерево— сбалансированное дерево для хранения и эффективного извлечения . Предложено Рудольфом Байером и ; является B⁺-деревом с записями, хранящимися в соответствии с Z-порядком, также называемым порядком Мортона. Z-порядок вычисляется путём побитового чередования ключей. Вставка, удаление и точечный запрос выполняются как с обычными B⁺-деревьями. Однако для выполнения поиска по диапазону в многомерных точечных данных должен быть предусмотрен алгоритм для вычисления из точки, обнаруженной в базе данных, следующего Z-значения, которое находится в диапазоне многомерного поиска. Первоначальный алгоритм решения этой ключевой проблемы был экспоненциально зависим от размерности и, следовательно, неосуществим («ПолучитьДальшеZ-адрес»[уточнить]). Решение этой важной части запроса диапазона UB-дерева[уточнить], линейного с длиной в битах z-адреса, было описано позже. Этот метод уже был описан в более старой статье. (ru) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Z-curve45.svg?width=300 |
| dbo:wikiPageID | 5786138 (xsd:integer) |
| dbo:wikiPageLength | 2189 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1076477721 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rudolf_Bayer dbr:Volker_Markl dbc:Search_trees dbr:B+_tree dbc:Database_index_techniques dbr:Z-order_(curve) dbr:Balanced_tree dbr:Multidimensional_data dbr:File:Z-curve45.svg |
| dbp:wikiPageUsesTemplate | dbt:Algorithm-stub dbt:CS-Trees |
| dcterms:subject | dbc:Search_trees dbc:Database_index_techniques |
| gold:hypernym | dbr:Tree |
| rdf:type | yago:Ability105616246 yago:Abstraction100002137 yago:Cognition100023271 yago:Know-how105616786 yago:Method105660268 yago:PsychologicalFeature100023100 dbo:Plant yago:Technique105665146 yago:WikicatDatabaseIndexTechniques |
| rdfs:comment | Der UB-Baum („Universal B-Tree“) wurde von Rudolf Bayer und vorgeschlagen und isteine 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 sowie für B-Bäume von Orenstein und Merrett) vorgeschlagen. (de) The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys. (en) UB-дерево— сбалансированное дерево для хранения и эффективного извлечения . Предложено Рудольфом Байером и ; является B⁺-деревом с записями, хранящимися в соответствии с Z-порядком, также называемым порядком Мортона. Z-порядок вычисляется путём побитового чередования ключей. Вставка, удаление и точечный запрос выполняются как с обычными B⁺-деревьями. Однако для выполнения поиска по диапазону в многомерных точечных данных должен быть предусмотрен алгоритм для вычисления из точки, обнаруженной в базе данных, следующего Z-значения, которое находится в диапазоне многомерного поиска. (ru) |
| rdfs:label | UB-Baum (de) UB-tree (en) UB-дерево (ru) |
| owl:sameAs | freebase:UB-tree yago-res:UB-tree wikidata:UB-tree dbpedia-de:UB-tree dbpedia-ru:UB-tree dbpedia-sr:UB-tree https://global.dbpedia.org/id/2KsvR |
| prov:wasDerivedFrom | wikipedia-en:UB-tree?oldid=1076477721&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Z-curve45.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:UB-tree |
| is dbo:knownFor of | dbr:Rudolf_Bayer |
| is dbo:wikiPageRedirects of | dbr:UB-Tree dbr:UB_tree |
| is dbo:wikiPageWikiLink of | dbr:Rudolf_Bayer dbr:List_of_data_structures dbr:T-tree dbr:Quadtree dbr:Red–black_tree dbr:Grid_file dbr:Z-order_curve dbr:PH-tree dbr:Spatial_database dbr:UB-Tree dbr:UB_tree |
| is dbp:knownFor of | dbr:Rudolf_Bayer |
| is foaf:primaryTopic of | wikipedia-en:UB-tree |
