Dynamic multi level indexing Using B-Trees And B+ Trees
- 1. Prof. Neeraj Bhargava PoojaDixit Department of Computer Science School of Engineering & System Science MDS, University Ajmer, Rajasthan, India 1
- 2. It isa self-balancing search tree Data is accessed from main memory in case of self balanced search tree like AVL Tree Huge amount of data will be accessed from disks During accessing of data, disk access time will be very high compared to main memory access time The main idea of using B-Trees is to reduce the number of disk accesses 2
- 3. Most ofthe tree operations (search, insert, delete etc) require O(h) disk accesses where h is the height of the tree B-tree is a fat tree Height is kept low by putting maximum possible keys in a B-Tree node Generally, a B-Tree node size is kept equal to the disk block size Since h is low for B-Tree, total disk accesses for most of the operations are reduced 3
- 4. All leavesare at same level A B-Tree is defined by the term minimum degree ‘t’ and the value of t depends upon disk block size Every node except root must contain at least t-1 keys Root may contain minimum 1 key All nodes (including root) may contain at most 2t – 1 keys Number of children of a node is equal to the number of keys in it plus 1 All keys of a node are sorted in increasing order Time complexity is O(Log n) 4
- 5.
- 6. Data pointercorresponding to a particular key value is stored along with that key value in the node of a B-tree. This reduces number of entries that is packed into a node of the tree Due to storing of Data Pointer the number of levels in a tree and search time of a record increases 6
- 7. Two orders of B+Tree Internal Node External or Leaf Node Eliminates the drawback of the B-Tree Stores data pointers only at the leaf nodes of the tree Structure of leaf nodes of a B+ tree is different from the structure of internal nodes of the B+ tree 7
- 8. Leaf nodesstore all the key values along with their corresponding data pointers to the disk file block, in order to access them Leaf nodes form the first level of index Internal nodes form the other levels of a multilevel index 8
- 9. 1) Each internalnode is of the form :- <P1, K1, P2, K2, …, Pc-1, Kc-1, Pc> where c <= a and each Pi is a tree pointer and, each Ki is a key value 2) Every internal node has : K1 < K2 < …. < Kc-1 3) For each search field values ‘X’ in the sub-tree pointed at by Pi, the following condition holds :- Ki-1 < X <= Ki, for 1 < i < c and, Ki-1 < X, for i = c 4) Each internal nodes has at most ‘a’ tree pointers. 5) The root node has, at least two tree pointers, while the other internal nodes have at least ceil(a/2) tree pointers each. 6) If any internal node has ‘c’ pointers, c <= a, then it has 'c – 1' key values. 9
- 10. ( Internal Nodein B+ Tree ) 10
- 11. 1) Each leafnode is of the form : <<K1, D1>, <K2, D2>, ….., <Kc-1, Dc-1>, Pnext> where c <= b and each Di is a data pointer and, each Ki is a key value and Pnext points to next leaf node in the B+ tree 2) Every leaf node has : K1 < K2 < …. < Kc-1, c <= b 3) Each leaf node has at least ceil(b/2) values. 4) All leaf nodes are at same level. 11
- 12.