15-415 Fall 2009B+ Tree Recitation.ppt

B+ Tree Recitation B+ Tree Recitation 15-415 Fall 2009B+ Tree Recitation Leman Akoglu9/30/2009 Schedule Overview of the provided B+ tree package Assignment 5 – the what’s Assignment 5 – the how’s * * B+ Tree Recitation B+ Tree Package – CompileRun make main ? compiles the source code ./main This starts you with an “empty” B+ tree * * B+ Tree Recitation B+ Tree Package – Existing Func.s P” to scan and print all the keys in the tree i to insert p to print a B+ tree page (p 1 prints the root) s to search and print the key S to search and print the key as well as its posting list T to print the B+ tree in in-order format x to exit * * B+ Tree Recitation B+ Tree Package – Main SRC files main.c parses the input scanTree.c scans the keys in the tree How leaf pages are accessed insert.c inserts a given key Looks for the insert position for a given key search.c to search and print the key How to traverse child nodes strdist.c returns distance between two keys * * B+ Tree Recitation B+ Tree Package – Preloaded make loaddb? compiles the source code and inserts keys from several example text files ./main starts you with a B+ tree to play with * * B+ Tree Recitation Assignment 5 – the what’s WHAT TO IMPLEMENT: ? 2 new functions Medium difficulty: range queries R key1 key2 print keys in-between r key1 key2 print count of keys in-between More difficult: all-pairs queries A ε print pairs of keys within ε distance a ε print count of pairs of keys within ε * * B+ Tree Recitation Assignment 5 – the how’s HOW TO START: All source files are in SRC Implement: 1) R ? keysInRange.c 2) r ? countKeysInRange.c 3) A ? allPairsWithin.c 4) a ? countAllPairsWithin.c Note: If you include .c files of your own, do not forget to update SRC/makefile * * B+ Tree Recitation Assignment 5 – the how’s HOW TO TEST: Run ‘make hw5’ no errors/warnings diff’s should be empty Sample test files in Tests generate test files for yourself if necess