| dbpedia-owl:abstract
|
- Der B-Baum ist eine in Datenbanken und Dateisystemen verwendete Daten- oder Indexstruktur. Sie ist eine Erweiterung des B-Baumes. Bei einem B-Baum werden die eigentlichen Datenelemente nur in den Blattknoten gespeichert, während die inneren Knoten lediglich Schlüssel enthalten. Die Schlüssel in den Verzeichnisseiten bezeichnet man auch als Separatoren. Der B+-Baum wird aus historischen Gründen manchmal auch als B*-Baum bezeichnet. Es gibt aber einen echt anderen B*-Baum, eine B-Baum-Variante mit einem Mindestfüllgrad von 2/3 durch eine verbesserte Split-Strategie. Ziel dieses Verfahrens ist es, die Zugriffszeiten auf die Datenelemente zu verbessern. Dazu muss man die Baumhöhe verringern, was bedeutet, dass der Verzweigungsgrad des Baumes wachsen muss. Da die maximale Speicherbelegung eines Knotens begrenzt ist, gewinnt man durch das Verlegen der Daten in die Blätter mehr Platz für Schlüssel bzw. Verzweigungen in den inneren Knoten. Dies gilt insbesondere bei der Speicherung komplexer Objekte, die deutlich mehr Speicher belegen als die Schlüssel, oder auch nicht über eine feste Größe verfügen. Die reduzierte Baumhöhe impliziert auch weniger innere Knoten. Diese können so leichter im Hauptspeicher gehalten werden, was die Leistung im wahlfreien Zugriff steigert. Ein weiteres Ziel kann sein, die Operation Bereichssuche zu verbessern, bei der alle Daten in einem gewissen Schlüsselintervall sequentiell durchlaufen werden. Werden die Daten nämlich ausschließlich in den Blättern abgelegt, muss der jeweils nächste Datensatz der Sequenz nicht wieder von der Wurzel aus gesucht werden. So muss für einen Komplettdurchlauf der Daten nur der erste Schlüssel gesucht werden, ein Großteil des Baumes wird nicht gelesen. Um Nachfolger und Vorgänger eines Blattknoten effizient (d.h. in konstanter Zeit) zu finden, müssen die Blätter in einer doppelt verketteten Liste miteinander verbunden sein. Dieses Feature wird häufig in die Definition des B-Baumes mit aufgenommen. Wesentlicher Vorteil eines externen Suchbaums (Daten nur in den Blättern) ist die Möglichkeit des Einsatzes von Sekundärindizes. Sie stellen einen weiteren – nach anderen Kriterien sortierbaren – Suchbaum auf denselben Daten zur Verfügung.
- In computer science, a B+ tree or B plus tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment. In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes. The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context—in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree. The NTFS, ReiserFS, NSS, XFS, and JFS filesystems all use this type of tree for metadata indexing. Relational database management systems such as IBM DB2, Informix, Microsoft SQL Server, Oracle 8, Sybase ASE, PostgreSQL, Firebird, MySQL and SQLite support this type of tree for table indices. Key-value database management systems such as CouchDB, Tokyo Cabinet support this type of tree for data access. InfinityDB is a concurrent BTree.
- En informática, un árbol-B es un tipo de estructura de datos de árboles. Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Su nombre se deriva de la incial del nombre de sus creadores: Byron Pérez y PlusEmma Mora. Ademas el signo "+" hace mención al la primera implementación de esta estructura: la cual fue utilizada por primera vez en el lenguaje C++ en un curso (llamada Algoritmos y Estructuras de Datos 2) mientras los creadores del árbol sacaba su titulo de Licienciatura. Un árbol-B+ es una variación de un árbol-B. En un árbol-B+, en contraste respecto un árbol-B, toda la información se guarda en las hojas. Los nodos internos sólo contienen claves y punteros. Todas las hojas se encuentran en el mismo, más bajo nivel. Los nodos hoja se encuentran unidos entre sí como una lista enlazada para permitir búsqueda secuencial. El número máximo de claves en un registro es llamado el orden del árbol-B+. El mínimo número de claves por registro es la mitad del máximo número de claves. Por ejemplo, si el orden de un árbol-B+ es n, cada nodo (exceptuando la raíz) debe tener entre n/2 y n claves. El número de claves que pueden ser indexadas usando un árbol-B+ está en función del orden del árbol y su altura. Para un árbol-B+ de orden n, con una altura h: Número máximo de claves es: Número mínimo de claves es:
- B+木（Template:Lang-en-short）は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント（「ブロック」などと呼ばれる。木構造におけるノードに相当）にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層（葉ノード）に格納され、内部ノードにはキーのみが格納される。 B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ の記憶装置があるとき、 の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い（2分探索木はブロック型でない記憶装置に適している）。 ReiserFS（UNIX、Linux）、XFS（IRIX、Linux）、JFS2（AIX、OS/2、Linux）、HammerFS（DragonFly BSD）、NTFSといったファイルシステムはいずれもB+木に類する構造をブロックのインデックス付けに使っている。関係データベースでも表のインデックスにこの種の木構造を使っていることが多い。
- Em ciência da computação, uma Árvore B+ é um tipo de árvore. Representa a ordenação de dados de uma maneira que permita uma inserção e remoção eficiente de elementos. É um índice dinâmico de multi-níveis com ligações máximas e mínimas no número de chaves em cada nodo. Os sistemas de ficheiros NTFS para o Microsoft Windows, o sistema de ficheiros ReiserFS para Unix, o XFS para IRIX e Linux, e o JFS2 para AIX, OS/2 e Linux, usam este tipo de árvore. Uma árvore B+ é uma variação da árvore B. Numa árvore-B+, contrastando com uma árvore-B, todos os dados são gravados nas folhas. Os nodos internos contêm apenas chaves e apontadores da árvore. Todas as folhas estão no mesmo nível mais baixo. Os nodos das folhas também estão ligados entre si como uma lista de ligações para efectuar consultas facilmente. O número máximo de apontadores num registo é chamado de ordem da árvore B+. O número mínimo de chaves por registo é metade do número máximo de chaves. Por exemplo, se a ordem de uma árvore B+ for n+1, cada nodo (excepto o da raiz) terá de ter entre (n+1)/2 e n chaves. Se n for um número primo, o número mínimo de chaves pode ser quer (n+1)/2 ou (n-1)/2, mas terá de ser o mesmo em toda a árvore. O número de chaves que poderá ser indexado ao usar a árvore B+ é uma função da ordem da árvore e da sua altura. Para uma árvore B+ de ordem n com uma altura h: O número máximo de nodos é O número mínimo de chaves é A árvore B+ foi descrita pela primeira vez em "Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173-189 (1972)". Uma extensão de uma árvore B+ é chamada de Árvore B# que usa a estrutura da árvore B+ e adiciona mais restrições.
- B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。 B+ 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。 B+ 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树（常简称为2-3 树）中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。 B+ 树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有的叶子节点在树中都在相同的级别上。B也可能代表Bayer，或者是波音（Boeing），因为他曾经工作于波音科学研究实验室。
- B+ дерево — структура данных, представляет собой сбалансированное дерево поиска. Является модификацией B-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах — ключи-разделители, содержащие диапазон изменения ключей для поддеревьев.
|
| rdfs:comment
|
- B+木（Template:Lang-en-short）は、キーを指定することで挿入・検索・削除が効率的に行える木構造の一種である。動的な階層型インデックスであり、各インデックスセグメント（「ブロック」などと呼ばれる。木構造におけるノードに相当）にはキー数の上限と下限がある。B+木はB木とは異なり、全てのレコードは木の最下層（葉ノード）に格納され、内部ノードにはキーのみが格納される。 B+木は、特にブロック型記憶装置での効率的データ検索に効果を発揮する。ブロックサイズ の記憶装置があるとき、 の倍数個のキーを格納するB+木は2分探索木に比較して非常に効率が良い（2分探索木はブロック型でない記憶装置に適している）。 ReiserFS（UNIX、Linux）、XFS（IRIX、Linux）、JFS2（AIX、OS/2、Linux）、HammerFS（DragonFly BSD）、NTFSといったファイルシステムはいずれもB+木に類する構造をブロックのインデックス付けに使っている。関係データベースでも表のインデックスにこの種の木構造を使っていることが多い。
- B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。 B+ 树在节点访问时间远远超过节点内部访问时间的时候，比可作为替代的实现有着实在的优势。这通常在多数节点在次级存储比如硬盘中的时候出现。通过最大化在每个内部节点内的子节点的数目减少树的高度，平衡操作不经常发生，而且效率增加了。这种价值得以确立通常需要每个节点在次级存储中占据完整的磁盘块或近似的大小。 B+ 背后的想法是内部节点可以有在预定范围内的可变数目的子节点。因此，B+ 树不需要象其他自平衡二叉查找树那样经常的重新平衡。对于特定的实现在子节点数目上的低和高边界是固定的。例如，在 2-3 B 树（常简称为2-3 树）中，每个内部节点只可能有 2 或 3 个子节点。如果节点有无效数目的子节点则被当作处于违规状态。 B+ 树的创造者 Rudolf Bayer 没有解释B代表什么。最常见的观点是B代表平衡(balanced)，因为所有的叶子节点在树中都在相同的级别上。B也可能代表Bayer，或者是波音（Boeing），因为他曾经工作于波音科学研究实验室。
- B+ дерево — структура данных, представляет собой сбалансированное дерево поиска. Является модификацией B-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах — ключи-разделители, содержащие диапазон изменения ключей для поддеревьев.
- Der B-Baum ist eine in Datenbanken und Dateisystemen verwendete Daten- oder Indexstruktur. Sie ist eine Erweiterung des B-Baumes. Bei einem B-Baum werden die eigentlichen Datenelemente nur in den Blattknoten gespeichert, während die inneren Knoten lediglich Schlüssel enthalten. Die Schlüssel in den Verzeichnisseiten bezeichnet man auch als Separatoren. Der B+-Baum wird aus historischen Gründen manchmal auch als B*-Baum bezeichnet.
- In computer science, a B+ tree or B plus tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment. In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.
- En informática, un árbol-B es un tipo de estructura de datos de árboles. Representa una colección de datos ordenados de manera que se permite una inserción y borrado eficientes de elementos. Es un índice, multinivel, dinámico, con un límite máximo y mínimo en el número de claves por nodo. Su nombre se deriva de la incial del nombre de sus creadores: Byron Pérez y PlusEmma Mora.
- Em ciência da computação, uma Árvore B+ é um tipo de árvore. Representa a ordenação de dados de uma maneira que permita uma inserção e remoção eficiente de elementos. É um índice dinâmico de multi-níveis com ligações máximas e mínimas no número de chaves em cada nodo. Os sistemas de ficheiros NTFS para o Microsoft Windows, o sistema de ficheiros ReiserFS para Unix, o XFS para IRIX e Linux, e o JFS2 para AIX, OS/2 e Linux, usam este tipo de árvore. Uma árvore B+ é uma variação da árvore B.
|
