B+ Tree uses in database indexing
- it is a balanced tree with d children but not binary tree. In practice, d will be larger — as large, in fact, as it takes to fill a disk block. So, it is more efficient as database index. Apart from that, B-trees are usually more shallow but wide than other trees with small d. A typical B-tree has a single-digit height, even with millions of entries. If your data is not large and can be served purely in memory, consider to use balanced binary tree like AVL Tree as it has better search time due to d=2 only.
- it doesn't have data record pointer(s) for the interior nodes. So, more keys can fit on a page of memory. Therefore, it will require fewer cache misses in order to access data that is on a leaf node.
- leaf nodes of B+ trees are linked. So doing a full scan of all objects in a tree requires just one linear pass through all the leaf nodes. And it is leaf nodes are sorted so it is great for range query.
B+ Tree vs B+ Tree (For Indexing)
- You can see B Tree stores key(s) and data record pointers in each nodes. So, frequently accessed nodes can lie closer to the root, and therefore can be accessed more quickly.
- On the other hand, it would require a traversal of every level in the tree. This full-tree traversal will likely involve more cache misses than the linear traversal of B+ leaves.
Usage
- Most RDBMS uses B+ Tree for indexing
- CouchDB also uses this
Red-black tree: balanced binary search tree
- binary tree means it has at most 2 children nodes under it.
- Search: O(log n)
- insertion and deletion: O(log n)
- Tracking the color of each node requires only 1 bit of information per node because there are only two colors.
AVL Tree vs Red Black Tree
Both red-black trees and AVL trees are the most commonly used balanced binary search trees and they support insertion, deletion and look-up in guaranteed O(logN) time.
Red-black trees are more general purpose. They do relatively well on add, remove, and look-up but AVL trees have faster look-ups at the cost of slower add/remove. Red-black tree is used in the following:
- Java: java.util.TreeMap , java.util.TreeSet .
- C++ STL: map, multimap, multiset.
- Linux kernel: completely fair scheduler, linux/rbtree.h
AVL trees store the balance factor at each node. This takes O(N) extra space. However, if we know that the keys that will be inserted in the tree will always be greater than zero, we can use the sign bit of the keys to store the colour information of a red-black tree. Thus, in such cases red-black tree takes O(1) extra space.