B+ tree | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

A B+ tree is an m-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children. A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves. The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, . This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node, typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree. B-tree There is no single paper introducing the B+ tree concept. Instead, the notion of maintaining all data in leaf nodes is repeatedly brought up as an interesting variant. Douglas Comer notes in an early survey of B-trees (which also covers B+ trees) that the B+ tree was used in IBM's VSAM data access software, and refers to an IBM published article from 1973. Graph (discrete mathematics)#Graph and Tree (data structure)#Terminology As with other trees, B+ trees can be represented as a collection of three types of nodes: root, internal, and leaf. These node types have the following properties: Individual nodes will have either record or children, but never both at the same time: this is the main distinction from a B-tree. The order or branching factor b of a B+ tree measures the capacity of internal nodes, i.e. their maximum allowed number of direct child nodes. This value is constant over the entire tree. Internal nodes have no records, but will always have nonzero children. The actual number of children m for a given internal node is constrained such that . Each child is then referred to as for , where represents the child node at natural number index . Leaf nodes have no children, and instead contain the elements of the B+ tree as records.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (11)

Related courses (29)

Related lectures (284)

Related MOOCs (14)

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

CH-244: Quantum chemistry

Introduction to Quantum Mechanics with examples related to chemistry

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

Plasma Physics: Introduction

Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.

Plasma Physics: Introduction

Learn the basics of plasma, one of the fundamental states of matter, and the different types of models used to describe it, including fluid and kinetic.

Plasma Physics: Applications

Learn about plasma applications from nuclear fusion powering the sun, to making integrated circuits, to generating electricity.

Understanding Chaos in Quantum Field Theories

Explores chaos in quantum field theories, focusing on conformal symmetry, OPE coefficients, and random matrix universality.

Hybrid Orbitals: Theory and Applications CH-244: Quantum chemistry

Covers the theory and applications of hybrid orbitals in molecular structures.

Non-Abelian Gauge Transformations

Explores Non-Abelian gauge transformations, emphasizing mathematical representations and field strengths.

Comparison of relational database management systems

The following tables compare general and technical information for a number of relational database management systems. Please see the individual products' articles for further information. Unless otherwise specified in footnotes, comparisons are based on the stable versions without any add-ons, extensions or external programs. The operating systems that the RDBMSes can run on. Information about what fundamental RDBMS features are implemented natively. Note (1): Currently only supports read uncommited transaction isolation.

B+ tree

B-tree

In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for nodes with more than two children. Unlike other self-balancing binary search trees, the B-tree is well suited for storage systems that read and write relatively large blocks of data, such as databases and s. B-trees were invented by Rudolf Bayer and Edward M.