A B*-tree is a tree data structure, a variety of B-tree used in the HFS and Reiser4 file systems, which requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with the node next to it. When both are full, then the two of them are split into three. It also requires the 'leftmost' key never to be used.

PropertyValue
dbpedia-owl:abstract
  • Der B*-Baum ist eine Daten- bzw. Indexstruktur in der Informatik und eine Variante des B-Baums, die 1973 von Donald Ervin Knuth vorgeschlagen wurde und sich vom B-Baum in der Forderung unterscheidet, dass Knoten mindestens zu 2/3 gefüllt sein müssen (anstatt nur 1/2 gefüllt). Dies wird vor allem durch eine veränderte Split-Strategie erreicht, bei der 2 volle Knoten auf 3 Knoten mit einem Füllgrad von 2/3 aufgeteilt werden. Der Name wird aus historischen Gründen oftmals für den B+-Baum verwendet, einer anderen B-Baum Variante, bei der Daten nur in den Blattknoten gespeichert werden, und durch die Verkettung der Blattknoten Bereichsanfragen effizienter unterstützt werden.
  • A B*-tree is a tree data structure, a variety of B-tree used in the HFS and Reiser4 file systems, which requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with the node next to it. When both are full, then the two of them are split into three. It also requires the 'leftmost' key never to be used. The term is not in general use today as the implementation was never looked on positively by the computer science community-at-large; most people use "B-tree" generically to refer to all the variations and refinements of the basic data structure.
  • Un árbol-B* es una estructura de datos de árbol, una variante de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2. Para mantener esto los nodos, en lugar de generar inmediatamente un nodo cuando se llenan, comparten sus claves con el nodo adyacente. Cuando ambos están llenos, entonces los dos nodos se transforman en tres. También requiere que la clave más a la izquierda no sea usada nunca. No se debe confundir un árbol-B* con un árbol-B+, en el que los nodos hoja del árbol están conectados entre sí a través de una lista enlazada, aumentando el coste de inserción para mejorar la eficiencia en la búsqueda.
  • B*木（Template:Lang-en-short）は、B木から派生した木構造の一種で、HFS や Reiser4 ファイルシステムで使われている。根ノード以外のノードは、B木のように1/2ではなく、2/3まで埋まった状態になる。このため、ノードがいっぱいになったとき即座に分割するのではなく、キーを次のノードと共有する。連続する2つのノードがいっぱいになると、それを3つのノードに分割する。また、常に左端のキーは使わずに残しておく。一般に総称して「B木」と呼ばれることが多く、「B*木」と呼ばれることは滅多にない。 B*木とB+木は異なる。後者は、葉ノードが連結されて連結リストを構成するようになっているものである。B+木は、挿入のコストを増大させて、検索を効率化したものである。 IEEE 0-8186-4212-2 1993 には B**木の定義も見られた。
  • B*-дерево — разновидность B-дерева, в которой каждый узел дерева заполнен не менее чем на 2/3 (в отличие от B-дерева, где этот показатель составляет 1/2). B+ дерево, удовлетворяющее таким требованиям называется B+*-деревом. B*-деревья предложили Р. Бэйер и Е. МакКрейт, изучавшие проблему компактности B-деревьев. B*-дерево относительно компактнее, так как каждый узел используется полнее. В остальном же этот вид деревьев не отличается от простого B-дерева. Для выполнения требования (заполненность узла не менее 2/3), приходится отказываться от простой процедуры разделения переполненного узла. Вместо этого происходит «переливание» в соседний узел. Если же и соседний узел заполнен, то ключи приблизительно поровну разделяются на 3 новых узла.
dbpedia-owl:wikiPageExternalLink
dcterms:subject
rdfs:comment
  • B*木（Template:Lang-en-short）は、B木から派生した木構造の一種で、HFS や Reiser4 ファイルシステムで使われている。根ノード以外のノードは、B木のように1/2ではなく、2/3まで埋まった状態になる。このため、ノードがいっぱいになったとき即座に分割するのではなく、キーを次のノードと共有する。連続する2つのノードがいっぱいになると、それを3つのノードに分割する。また、常に左端のキーは使わずに残しておく。一般に総称して「B木」と呼ばれることが多く、「B*木」と呼ばれることは滅多にない。 B*木とB+木は異なる。後者は、葉ノードが連結されて連結リストを構成するようになっているものである。B+木は、挿入のコストを増大させて、検索を効率化したものである。 IEEE 0-8186-4212-2 1993 には B**木の定義も見られた。
  • Der B*-Baum ist eine Daten- bzw. Indexstruktur in der Informatik und eine Variante des B-Baums, die 1973 von Donald Ervin Knuth vorgeschlagen wurde und sich vom B-Baum in der Forderung unterscheidet, dass Knoten mindestens zu 2/3 gefüllt sein müssen (anstatt nur 1/2 gefüllt). Dies wird vor allem durch eine veränderte Split-Strategie erreicht, bei der 2 volle Knoten auf 3 Knoten mit einem Füllgrad von 2/3 aufgeteilt werden.
  • A B*-tree is a tree data structure, a variety of B-tree used in the HFS and Reiser4 file systems, which requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with the node next to it. When both are full, then the two of them are split into three. It also requires the 'leftmost' key never to be used.
  • Un árbol-B* es una estructura de datos de árbol, una variante de Árbol-B utilizado en los sistemas de ficheros HFS y Reiser4, que requiere que los nodos no raíz estén por lo menos a 2/3 de ocupación en lugar de 1/2. Para mantener esto los nodos, en lugar de generar inmediatamente un nodo cuando se llenan, comparten sus claves con el nodo adyacente. Cuando ambos están llenos, entonces los dos nodos se transforman en tres. También requiere que la clave más a la izquierda no sea usada nunca.
  • B*-дерево — разновидность B-дерева, в которой каждый узел дерева заполнен не менее чем на 2/3 (в отличие от B-дерева, где этот показатель составляет 1/2). B+ дерево, удовлетворяющее таким требованиям называется B+*-деревом. B*-деревья предложили Р. Бэйер и Е. МакКрейт, изучавшие проблему компактности B-деревьев. B*-дерево относительно компактнее, так как каждый узел используется полнее. В остальном же этот вид деревьев не отличается от простого B-дерева.
rdfs:label
  • B*-Baum
  • Árbol-B*
  • B*-tree
  • B*木
  • B*-дерево
owl:sameAs
foaf:page
is dbpedia-owl:wikiPageRedirects of
is dbpprop:directoryStruct of
is owl:sameAs of
is foaf:primaryTopic of