B-Tree
B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.
A B-tree of order M is an M-ary tree with the following properties:
Variants of B-Tree
The term B-tree may refer to a specific design or it may refer to a general class of designs. In the narrow sense, a B-tree stores keys in its internal nodes but need not store those keys in the records at the leaves. The general class includes variations such as the B+-tree and the B*-tree.
In the B+-tree, copies of the keys are stored in the internal nodes; the keys and records are stored in leaves; in addition, a leaf node may include a pointer to the next leaf node to speed sequential access.
The B*-tree balances more neighboring internal nodes to keep the internal nodes more densely packed.This variant requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with a node next to it. When both nodes are full, then the two nodes are split into three.
Counted B-trees store, with each pointer within the tree, the number of elements in the subtree below that pointer. This allows rapid searches for the Nth record in key order, or counting the number of records between any two records, and various other related operations.
M-way Tree
A B-tree of order m is a m-way tree that satisfies the following conditions.
Email-Id : vinay.kr.saini@gmail.com
Connect with me
Visit My Blog: http://vinay-kumar-saini.blogspot.in/
B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree is a generalization of a binary search tree in that a node can have more than two children. Unlike self-balancing binary search trees, the B-tree is optimized for systems that read and write large blocks of data. It is commonly used in databases and filesystems.
A B-tree of order M is an M-ary tree with the following properties:
- Every B-tree is of some "order n", meaning nodes contain from n to 2n keys (so nodes are always at least half full of keys), and n+1 to 2n+1 pointers, and n can be any number.
- Keys are kept in sorted order within each node. A corresponding list of pointers are effectively interspersed between keys to indicate where to search for a key if it isn't in the current node.
Variants of B-Tree
The term B-tree may refer to a specific design or it may refer to a general class of designs. In the narrow sense, a B-tree stores keys in its internal nodes but need not store those keys in the records at the leaves. The general class includes variations such as the B+-tree and the B*-tree.
In the B+-tree, copies of the keys are stored in the internal nodes; the keys and records are stored in leaves; in addition, a leaf node may include a pointer to the next leaf node to speed sequential access.
The B*-tree balances more neighboring internal nodes to keep the internal nodes more densely packed.This variant requires non-root nodes to be at least 2/3 full instead of 1/2. To maintain this, instead of immediately splitting up a node when it gets full, its keys are shared with a node next to it. When both nodes are full, then the two nodes are split into three.
Counted B-trees store, with each pointer within the tree, the number of elements in the subtree below that pointer. This allows rapid searches for the Nth record in key order, or counting the number of records between any two records, and various other related operations.
M-way Tree
A B-tree of order m is a m-way tree that satisfies the following conditions.
- Every node has < m children.
- Every internal node (except the root) has <m/2 children.
- The root has >2 children.
- An internal node with k children contains (k-1) ordered keys. The leftmost child contains keys less than or equal to the first key in the node. The second child contains keys greater than the first keys but less than or equal to the second key, and so on.
Vinay Kumar Saini
Assistant Professor (I.T Department)
Maharaja Agrasen Institute of Technology (MAIT)
Sector-22, Rohini, Delhi-110086, IndiaEmail-Id : vinay.kr.saini@gmail.com
Connect with me
Visit My Blog: http://vinay-kumar-saini.blogspot.in/
No comments:
Post a Comment