CompSci 100E39.1Memory Modelÿ For this course: Assume Uniform Access Timeþ All elements in an array accessible with same time costþ Reality is somewhat differentÿ Memory Hierarchy (in order of decreasing speed)þ Registersþ On (cpu) chip cache memoryþ Off chip cache memoryþ Main memoryþ Virtual memory (automatically managed use of disk)þ Explicit disk I/Oþ CD-ROM, network file system, tapes, other slow devicesÿ All but last two managed by systemþ Need to be aware, but can do little to manipulate others directlyþ Promote locality?CompSci 100E39.2Cost of Disk I/Oÿ Disk access 10,000 to 100,000 times slower thanmemory accessþ Do almost anything (almost!) in terms of computation toavoid an extra disk accessþ Performance penalty is hugeÿ B-Trees designed to be used with disk storageþ Typically used with database applicationsþ Many different variationsþ Will present basic ideas hereÿ Want broad, not deep treesþ Even log N disk accesses can be too manyCompSci 100E39.3External Methodsÿ Disk use requires special considerationþ Timing Considerations (already mentioned)þ Writing pointers to disk?þ What do values mean when read in at a differenttime/different machine?ÿ General Properties of B-Treesþ All Leaves Have Same Depthþ Degree of Node >2þ (maybe hundreds or thousands)ÿ Not a Binary Tree, but is a Search Treeþ There are many implementations...þ Will use examples with artificially small numbers toillustrateCompSci 100E39.4Rules of B-Treesÿ Rules1. Every node (except root) has at least MINIMUM entries2. The MAXIMUM number of node entries is 2*MINIMUM3. The entries of each B-tree are stored, sorted4. The number of sub-trees below a non-leaf node is onegreater than the number of node entries5. For non leaves:þ Entry at index k is greater than all entries in sub-tree kþ Entry at index k is less than all entries in sub-tree k+16. Every leaf in a B-tree has the same depthCompSci 100E39.5ExampleExample B Tree (MAX = 2)[6]******[2 4] [9]*** ***** * **** * *[1] [3] [5] [7 8] [10]CompSci 100E39.6Search in B-Treeÿ Every Child is Also the Root of a Smaller B-Treeÿ Possible internal node implementationclass BTNode { //ignoring ref on disk issueint myDataCount;int myChildCount;KeyType[] myKeys[MAX+1];BTNode[] myChild[MAX+2]}ÿ Search pseudo-code:boolean isInBTree(BTNode t, KeyType key);1. Search through t.myKeys until t.myKeys[k] >= key2. If t.myData[k] == key, return true3. If t.isLeaf() return false4. return isInBtree(t.myChild[k])CompSci 100E39.7Find ExampleExample Find i n B-Tree (MAX = 2)Finding 10[6 17]** *** *** *** *** *[4] [12] [19 22]** ** ***** * * **********[2 3] [5] [10] [16] [18] [20] [25]CompSci 100E39.8B-Tree Insertionÿ Insertion Gets a Little Messyþ Insertion may cause rule violationþ “Loose” Insertion (leave extra space) (+1)þ Fixing Excess Entriesÿ Insert Fixþ Splitþ Move up middleþ Height gained only at rootÿ Look at some examplesCompSci 100E39.9Insertion Fixÿ (MAX = 4) Fixing Child with Excess Entry: Split[9 28] BEFORE******** *** *[3 4] [13 16 19 22 25] [33 40]*** * **** * ****** * * * * * * ****** * * * * * * * * *[2 3][4 5][7 8][11 12][14 15][17 18][20 21][23 24][26 27][31 32][34 35][50 51][9 19 28] AFTER*** **** **** **** *[3 4] [13 16] [22 25] [33 40]*** * ** ** * ****** * ** ** * ****** * * * * * * * * *[2 3][4 5][7 8][11 12][14 15][17 18][20 21][23 24][26 27][31 32][34 35][50 51]CompSci 100E39.10Insertion Fix (MAX= 2) Another Fix[6 17] BEFORE***** *** *[4] [12] [18 19 22][] STEP 2**[6 17 19]** * *** * *** **[4] [12] [18] [22][6 17 19] STEP 1************[4] [12] [18] [22][17] AFTER****[6] [19]** **********[4] [12] [18] [22]CompSci 100E39.11B-Tree Removalÿ Removeþ Loose Removeþ If rules violated: Fixo Borrow (rotation)o Joinÿ Examples left to the “reader”CompSci 100E39.12B-Treesÿ Many variationsþ Leaf node often different from internal nodeþ Only leaf nodes carry all data (internal nodes: keys only)þ These examples didn’t distinguish keys from dataþ Design to have nodes fit disk blocko (hardware dependent)ÿ The Big Pictureþ Details can be worked out to match your needsþ Can do a lot of computation to avoid a disk
View Full Document