Ch4.6B+TreeInvertedFileIndex.pptVIP

* §6 B+ Trees 【Definition】A B+ tree of order M is a tree with the following structural properties: 1 The root is either a leaf or has between 2 and M children. 2 All nonleaf nodes except the root have between ?M/2? and M children. 3 All leaves are at the same depth. Assume each nonroot leaf also has between ?M/2? and M children. 12 15 25 31 41 59 84 91 1,4,8,11 12,13 15,18,19 21,24 25,26 31,38 41,43,46 48,49,50 59,68 72,78 84,88 91,92,99 21 48 72 A B+ tree of order 4 2-3-4 tree All the actual data are stored at the leaves. Each interior node contains M pointers to the children. And M ? 1 smallest key values in the subtrees except the 1st one. 1/11 §6 B+ Trees A B+ tree of order 3 2-3 tree 8,11,12 16,17 22,23,31 41,52 58,59,61 16:? 41:58 22:? ? Find: 52 ? Insert: 18 16,17,18 ? Insert: 1 ? 11,12 22,23,31 41,52 58,59,61 11:16 41:58 22:? 16,17,18 1, 8 ? Insert: 19 ? 11,12 22,23,31 41,52 58,59,61 11:? 41:58 16:22 16,17 1, 8 18,19 18:? ? Insert: 28 2/11 §6 B+ Trees 11,12 22,23 41,52 58,59,61 11:? 58:? 16:? 16,17 1, 8 18,19 18:? 28,31 28:? 22:? 41:? ? Insert: 70 First find a sibling with 2 keys and adjust. Keep more nodes full. ? Deletion is similar to insertion except that the root is removed when it loses two children. 3/11 §6 B-Trees For a general B-tree of order M Btree Insert ElementType X, Btree T Search from root to leaf for X and find the proper leaf node; Insert X; while this node has M+1 keys split it into 2 nodes with ? M+1 /2? and ? M+1 /2 ? keys, respectively; if this node is the root create a new root with two children; check its parent; Depth M, N O ?log?M/2? N ? T O M T M, N O M/log M log N TFind M, N O log N Note: The best choice of M is 3 or 4. Home work: p.138 4.36 Access a 2-3 tree 4/11 Inverted File Index How can I find in which retrieved web pages that include Computer Science? 5/11 Inverted File Index ? Solution 1: Scan each page for the string Computer Science. How did Google do? 6/11 Inverted F