B+ tree
An m-ary rooted tree / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short, summarize this topic like I'm... Ten years old or a College student
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.
| B+ tree | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | Tree (data structure) | |||||||||||||||
| Time complexity in big O notation | ||||||||||||||||
| ||||||||||||||||
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, typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.