Showing posts with label trees. Show all posts
Showing posts with label trees. Show all posts
Saturday, February 14, 2015
What are B Trees
- B+ tree is a variation of B-tree data structure. In a B+ tree, data pointers are stored only at the leaf nodes of the tree. In a B+ tree structure of a leaf node differ from the structure of internal nodes.
- The leaf nodes have an entry for every value of the search field, along with a data pointer to the record (or to the block that contains this record).
- The leaf nodes of the B+ tree are linked together to provide ordered access on the search field to the records.
- Internal nodes of a B+ tree are used to guide the search.
- Some search field values from the leaf nodes are repeated in the internal nodes of the B+ tree.
Also Read: What are B-Trees?
Also Read: C Program for AVL Tree Implementation
Structure of Internal node
The structure of the internal nodes is shown below:
- Each internal node is of the form < P1, K1, P2, K2 . . . Pn-1, Kn-1, Pn > where Ki is the key and Pi is a tree pointer
- Within each internal node, K1 < K2, . . . < Kn-1
- For all search field value x in the subtree pointed at by Pi, we have Ki-1 x <= Ki.
- Each internal node has at most p tree pointers.
- Each internal node, except the root, has at least ⌈(P/2)⌉ tree pointers.
Structure of a leaf node
The structure of a leaf node of a B+ tree is shown below:
- Each leaf node is of the form <<K1, P1>, <K2, P2> . . . <Kn-1, Pn-1>, Pnext>
- Within each leaf node, K1 < K2 . . . < Kn-1.
- Pi is a data pointer that points to the record whose search field value is Ki.
- Each leaf node has at least ⌈(P/2)⌉ values.
- All leaf nodes are at the same level.
Friday, February 13, 2015
What are B Trees
B-tree is another very popular search tree. The node in a binary tree like AVL tree contains only one record. AVL tree is commonly stored in primary memory. In database application, where huge volume of data is handled, the search tree cannot be accommodated in primary memory. B-trees are primarily meant for secondary storage.
A B-tree is a M-way tree. An M-way tree can have maximum of M children.
Also Read: C Program for AVL Tree Implementation
Also Read: C Program to Create a Binary Tree Using Recursion [Linked Representation]
An M-way tree contains multiple keys in a node. This leads to reduction in overall height of the tree. If a node of M-way tree holds K number of keys then it will have K+1 children.
Definition
A B-tree of order M is a M-way search tree with the following properties:
1. The root can have 1 to M-1 keys.
2. All nodes (except the root) have between [(M-1)/2] and M-1 keys.
3. All leaves are at the same depth.
4. If a node has t number of children then it must have (t-1) number of keys.
5. Keys of a node are sorted in ascending order.
6. K0, K1, K2. . . Kn-1 are the keys stored in the node. Subtrees are pointed by P0, P1 . . . Pn then K0>= all keys of the subtree P1
.
.
.
.
Kn-1 >= all keys of the subtree Pn-1
Kn-1 < all keys of the subtree Pn
An example of B-tree of order 4 is shown below:
Representation of a node of B-tree
# define MAX 5
struct node;
struct pair
{
node *next;
int key;
};
struct node
{
node *first;
node *father;
pair data [MAX];
int noofkeys;
};
- Structure pair is being used to combine a key and the associated tree pointer.
- Class node can store a maximum of MAX pairs of (key, next). A node with MAX number of keys will give rise to MAX + 1 ways. The additional tree pointer is designated as ‘first’.
- ‘nooofkeys’ gives the actual number of keys stored in a node.
- The pointer ‘father’ points to the father of a node. ‘father’ pointer will be NULL for the root node.
Please share this article if you like it. If you find anything incorrect or missing above then mention it by commenting below.
Subscribe to:
Posts (Atom)