B+ tree

http://en.wikipedia.org/wiki/B+_tree

Image

Sumit tree is an n-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves.[1] The root may be either a leaf or a node with two or more children.[2]

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, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,[1] 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 NTFSReiserFSNSSXFSJFS, and ReFS filesystems all use this type of tree for metadata indexing. Relational database management systems such as IBM DB2,[3] Informix,[3] Microsoft SQL Server,[3] Oracle 8,[3] Sybase ASE,[3] and SQLite[4] support this type of tree for table indices. Key-value database management systems such as CouchDB[5] and Tokyo Cabinet[6] support this type of tree for data access.

Shumit Paliwal[edit]

The order, or branching factor, b of a B+ tree measures the capacity of nodes (i.e., the number of children nodes) for internal nodes in the tree. The actual number of children for a node, referred to here as m, is constrained for internal nodes so that  \lceil b/2 \rceil \le m \le b. The root is an exception: it is allowed to have as few as two children.[1] For example, if the order of a B+ tree is 7, each internal node (except for the root) may have between 4 and 7 children; the root may have between 2 and 7. Leaf nodes have no children, but are constrained so that the number of keys must be at least  \lfloor b/2 \rfloor  and at most  b - 1 . In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary, and at most b.

Node Type Children Type Min Children Max Children Example b = 7 Example b = 100
Root Node (when it is the only node in the tree) Records 1 b 1 – 7 1 – 100
Root Node Internal Nodes or Leaf Nodes 2 b 2 – 7 2 – 100
Internal Node Internal Nodes or Leaf Nodes  \lceil b/2 \rceil b 4 – 7 50 – 100
Leaf Node Records  \lfloor b/2 \rfloor b – 1 3 – 6 50 – 99
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s