B+ tree - Wikipedia, the free encyclopedia
A B+ 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.
http://jxlilin.blogspot.in/2013/11/b-tree-implementation-in-java.html
The most commonly implemented form of the B-Tree is the B+ Tree. The difference between them is that the internal nodes of B+ tree do not store records, they are used for navigation only.
★ Definition of B+ Tree
A B+ Tree of order m has these properties:
- The root is either a leaf or has at least two children;
- Each internal node, except for the root, has between ⎡m/2⎤ and m children;
- Internal nodes do not store record, only store key values to guild the search;
- Each leaf node, has between ⎡m/2⎤ and m keys and values;
- Leaf node store keys and records or pointers to records;
- All eaves are at the same level in the tree, so the tree is always height balanced.
Search
http://www.quora.com/B+-Trees
http://www.quora.com/What-are-the-differences-between-B+Tree-and-B-Tree
A B+ tree only stores data in the leaf nodes.
With no data in the interior nodes the fan-out can be higher than with a B tree, tree depth shorter, reads from secondary storage lower, cache hit rate on intermediate nodes better, and time to data faster.
B- trees (called Btree not B minus tree) keeps key values and corresponding records in the same node whereas all the records are stored in the leaves of B+tree. (If you search a value and it matches with a internal node for B- tree you might get it directly from the node but for B+tree you need to go leaves anyway for the exact record ) In that way each non leaf node is able to store more pointer in the places of records. It gives lower height trees compared to B- trees in which it results some specific pros and cons.
http://en.wikibooks.org/wiki/Algorithm_Implementation/Trees/B%2B_tree
Java Code:
http://www.waltdestler.com/downloads/BPTree.java
https://himmele.googlecode.com/svn/trunk/Algorithms%20and%20Data%20Structures/BPlusTree/src/BPlusTree.java
Read full article from B+ tree - Wikipedia, the free encyclopedia
A B+ 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.
http://jxlilin.blogspot.in/2013/11/b-tree-implementation-in-java.html
The most commonly implemented form of the B-Tree is the B+ Tree. The difference between them is that the internal nodes of B+ tree do not store records, they are used for navigation only.
★ Definition of B+ Tree
A B+ Tree of order m has these properties:
- The root is either a leaf or has at least two children;
- Each internal node, except for the root, has between ⎡m/2⎤ and m children;
- Internal nodes do not store record, only store key values to guild the search;
- Each leaf node, has between ⎡m/2⎤ and m keys and values;
- Leaf node store keys and records or pointers to records;
- All eaves are at the same level in the tree, so the tree is always height balanced.
Search
- Do binary search on keys in current node.
- When current node is a leaf node:
- If search key is found, then return record.
- If search key is not found, then report an unsuccessful search.
- When current node is a internal node:
- If search key < key_0, then repeat the search process on the first branch of current node.
- If search key >= key_last, then repeat the search process on the last branch of current node.
- Otherwise, find the first key_i >= key, and repeat the search process on the (i+1) branch of current node.
Insertion
- Perform a search to determine which leaf node the new key should go into.
- If the node is not full, insert the new key, done!
- Otherwise, split the leaf node.
- Allocate a new leaf node and move half keys to the new node.
- Insert the new leaf's smallest key into the parent node.
- If the parent is full, split it too, repeat the split process above until a parent is found that need not split.
- If the root splits, create a new root which has one key and two children.
Deletion
- Perform a search to determine which leaf node contains the key.
- Remove the key from the leaf node.
- If the leaf node is at least half-full, done!
- If the leaf node as L is less than half-full:
- Try to borrow a key from sibling node as S (adjacent node with same parent)
- If S is L's left sibling, then borrow S's last key, and replace their parent navigate key with this borrowed key value.
- If S is L's right sibling, then borrow S's first key, and replace their parent navigate key with S's second key value.
- If can not borrow a key from sibling node, then merge L and sibling S
- After merged L and S, delete their parent navigate key and proper child pointer.
- Repeat the borrow or merge operation on parent node, perhaps propagate to root node and decrease the height of the tree.
http://www.quora.com/What-are-the-differences-between-B+Tree-and-B-Tree
A B+ tree only stores data in the leaf nodes.
With no data in the interior nodes the fan-out can be higher than with a B tree, tree depth shorter, reads from secondary storage lower, cache hit rate on intermediate nodes better, and time to data faster.
- B+ trees don't store data pointer in interior nodes, they are ONLY stored in leaf nodes. This is not optional as in B-Tree. This means that interior nodes can fit more keys on block of memory.
- The leaf nodes of B+ trees are linked, so doing a linear scan of all keys will requires just one pass through all the leaf nodes. A B tree, on the other hand, would require a traversal of every level in the tree. This property can be utilized for efficient search as well since data is stored only in leafs.
B- trees (called Btree not B minus tree) keeps key values and corresponding records in the same node whereas all the records are stored in the leaves of B+tree. (If you search a value and it matches with a internal node for B- tree you might get it directly from the node but for B+tree you need to go leaves anyway for the exact record ) In that way each non leaf node is able to store more pointer in the places of records. It gives lower height trees compared to B- trees in which it results some specific pros and cons.
http://en.wikibooks.org/wiki/Algorithm_Implementation/Trees/B%2B_tree
Java Code:
http://www.waltdestler.com/downloads/BPTree.java
https://himmele.googlecode.com/svn/trunk/Algorithms%20and%20Data%20Structures/BPlusTree/src/BPlusTree.java
Read full article from B+ tree - Wikipedia, the free encyclopedia
