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-5th Edition,Oct 4,2006 12.17 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 12.17 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 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 K1-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<..<Km-1 Database System Concepts-5th Edition,Oct 4,2006 12.18 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 12.18 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 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
Leaf Nodes in B-Trees Properties of a leaf node: For i=1,2,...,n-1,pointer P either points to a file record with search- key value K,or to a bucket of pointers to file records,each record having search-key value Ki.Only need bucket structure if search-key does not form a primary key. If Li,Li are leaf nodes and i<j,L's search-key values are less than Li's search-key values Pr points to next leaf node in search-key order Brighton Downtown leaf node A-212 Brighton 750 A-101 Downtown 500 A-110 Downtown 600 account file Database System Concepts-5th Edition,Oct 4,2006 12.19 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 12.19 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 Leaf Nodes in B+ -Trees For i = 1, 2, . . ., n–1, pointer Pi either points to a file record with searchkey value Ki , or to a bucket of pointers to file records, each record having search-key value Ki . Only need bucket structure if search-key does not form a primary key. If Li , Lj are leaf nodes and i < j, Li ’s search-key values are less than Lj ’s search-key values Pn points to next leaf node in search-key order Properties of a leaf node:
Non-Leaf Nodes in B+-Trees Non leaf nodes form a multi-level sparse index on the leaf nodes.For a non-leaf node with m pointers: All the search-keys in the subtree to which P points are less than K1 For 2<is n-1,all the search-keys in the subtree to which P points have values greater than or equal to K_1 and less than K All the search-keys in the subtree to which P points have values greater than or equal to K1 P1 K1 P2 Pn-1 K1-1 Pn Database System Concepts-5th Edition,Oct 4,2006 12.20 ©Silberschat乜，Korth and Sudarshan
Database System Concepts - 5 12.20 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 Non-Leaf Nodes in B+ -Trees Non leaf nodes form a multi-level sparse index on the leaf nodes. For a non-leaf node with m pointers: All the search-keys in the subtree to which P1 points are less than K1 For 2 i n – 1, all the search-keys in the subtree to which Pi points have values greater than or equal to Ki–1 and less than Ki All the search-keys in the subtree to which Pn points have values greater than or equal to Kn–1
Example of a B*-tree Perryridge Mianus Redwood Brighton Downtown Mianus Perryridge Redwood Round Hill B+-tree for account file(n=3) Database System Concepts-5th Edition,Oct 4,2006 12.21 @Silberschatz,Korth and Sudarshan
Database System Concepts - 5 12.21 ©Silberschatz, Korth and Sudarshan th Edition, Oct 4, 2006 Example of a B+ -tree B+ -tree for account file (n = 3)