B*-Tree Index Files B+-tree indices are an alternative to indexed-sequential files. Disadvantage of indexed-sequential files performance degrades as file grows,since many overflow blocks get created. Periodic reorganization of entire file is required. Advantage of B+-tree index files: automatically reorganizes itself with small,local,changes, in the face of insertions and deletions. Reorganization of entire file is not required to maintain performance. (Minor)disadvantage of B+-trees: extra insertion and deletion overhead,space overhead. Advantages of B+-trees outweigh disadvantages B+-trees are used extensively Database System Concepts-6th Edition 11.17 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 11.17 ©Silberschatz, Korth and Sudarshan th Edition B+ -Tree Index Files Disadvantage of indexed-sequential files performance degrades as file grows, since many overflow blocks get created. Periodic reorganization of entire file is required. Advantage of B+ -tree index files: automatically reorganizes itself with small, local, changes, in the face of insertions and deletions. Reorganization of entire file is not required to maintain performance. (Minor) disadvantage of B+ -trees: extra insertion and deletion overhead, space overhead. Advantages of B+ -trees outweigh disadvantages B+ -trees are used extensively B+ -tree indices are an alternative to indexed-sequential files
Example of B+-Tree Mozart Root node Einstein Gold Internal nodes Leaf nodes- Brandt Califieri Crick Einstein ElSaid Gold Katz Kim Mozart Singh 10101 Srinivasan Comp.Sci. 65000 12121 Wu Finance 90000 15151 Mozart Music 40000 22222 Einstein Physies 95000 32343 E☒Said History 80000 33456 Gold Physics 87000 45565 Katz Comp.Sci. 75000 58583 Califieri History 60000 76543 Singh Finance 80000 76766 Crick Biology 72000 83821 Brandt Comp.Sci. 92000 98345 K的m Elec.Eng. 80000 Database System Concepts-6th Edition 11.18 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 11.18 ©Silberschatz, Korth and Sudarshan th Edition Example of B+ -Tree
B+-Tree Index Files (Cont.) A B+-tree is a rooted tree satisfying the following properties: All paths from root to leaf are of the same length Each node that is not a root or a leaf has betweenn/2and n children. A leaf node has between(n-1)/2 and n-1 values Special cases: If the root is not a leaf,it has at least 2 children. If the root is a leaf(that is,there are no other nodes in the tree),it can have between 0 and (n-1)values. Database System Concepts-6th Edition 11.19 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 11.19 ©Silberschatz, Korth and Sudarshan th Edition B+ -Tree Index Files (Cont.) All paths from root to leaf are of the same length Each node that is not a root or a leaf has between n/2 and n children. A leaf node has between (n–1)/2 and n–1 values Special cases: If the root is not a leaf, it has at least 2 children. If the root is a leaf (that is, there are no other nodes in the tree), it can have between 0 and (n–1) values. A B+ -tree is a rooted tree satisfying the following properties:
B+-Tree Node Structure Typical node P1 K1 P2 。。 Pn-1 Kn-1 Pn Ki are the search-key values P are pointers to children(for non-leaf nodes)or pointers to records or buckets of records (for leaf nodes) The search-keys in a node are ordered K1<K2<K3<..<Kn-1 (Initially assume no duplicate keys,address duplicates later) Database System Concepts-6th Edition 11.20 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 6 11.20 ©Silberschatz, Korth and Sudarshan th Edition B+ -Tree Node Structure Typical node Ki are the search-key values Pi are pointers to children (for non-leaf nodes) or pointers to records or buckets of records (for leaf nodes). The search-keys in a node are ordered K1 < K2 < K3 < . . . < Kn–1 (Initially assume no duplicate keys, address duplicates later)
Leaf Nodes in B+-Trees Properties of a leaf node: For i=1,2,...,n-1,pointer P points to a file record with search-key value Ki, If Li,Li are leaf nodes and i<j,Li's search-key values are less than or equal to L's search-key values P,points to next leaf node in search-key order leaf node Brandt Califieri Crick Pointer to next leaf node 10101 Srinivasan Comp.Sci. 65000 12121 Wu Finance 90000 15151 Mozart Music 40000 22222 Einstein Physics 95000 32343 El Said History 80000 33456 Gold Physics 87000 45565 Katz Comp.Sci. 75000 58583 Califieri History 60000 76543 Singh Finance 80000 76766 Crick Biology 72000 83821 Brandt Comp.Sci. 92000 98345 Kim Elec.Eng. 80000 Database System Concepts-6th Edition 11.21 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 6 11.21 ©Silberschatz, Korth and Sudarshan th Edition Leaf Nodes in B+ -Trees For i = 1, 2, . . ., n–1, pointer Pi points to a file record with search-key value Ki , If Li , Lj are leaf nodes and i < j, Li ’s search-key values are less than or equal to Lj ’s search-key values Pn points to next leaf node in search-key order Properties of a leaf node: