Multilevel Index(Cont.) index data block 0 block 0 : data index block 1 block 1 outer index inner index Database System Concepts-7th Edition 14.13 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 14.13 ©Silberschatz, Korth and Sudarshan th Edition Multilevel Index (Cont.)
Indices on Multiple Keys ■Composite search key E.g.,index on instructorrelation on attributes(name,ID) Values are sorted lexicographically E.g.(John,12121)<(John,13514)and (John,13514)<(Peter,.11223) Can query on just name,or on (name,ID) Database System Concepts-7th Edition 14.16 ©Silberscha乜，Korth and Sudarshan
Database System Concepts - 7 14.16 ©Silberschatz, Korth and Sudarshan th Edition Indices on Multiple Keys ▪ Composite search key • E.g., index on instructor relation on attributes (name, ID) • Values are sorted lexicographically ▪ E.g. (John, 12121) < (John, 13514) and (John, 13514) < (Peter, 11223) • Can query on just name, or on (name, ID)
Example of B+-Tree Mozart Root node Einstein Gold Srinivasan Internal nodes Leaf nodes- Brandt Califieri Crick Einstein El Said Gold Katz Kim- Mozart Singh Srinivasan Wu 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-7th Edition 14.18 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 14.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 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. Database System Concepts-7th Edition 14.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 14.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 K 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-7th Edition 14.20 @Silberschatz,Korth and Sudarshan
Database System Concepts - 7 14.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)