CPSC 2120 - DAY 11 MAY 30, 2016 ================================================================================ B TREES - INSERTING NODES ------------------------- when a node splits, it will split immediately to the right M - number of children that an interior node can have L - number of values that each leaf can hold Choosing M Each Node represents a disk block ex. each block 8K = 2^13 bytes each interior node can hold M - 1 keys and M disk references Assume a key requires 32 bytes Assume a disk reference requires 4 bytes (. _ . _ .) ^ ^ ^ | | | --------- Disk references are the pointers to the leafs on the disk Keys are _ 's. ex (.10._.) key would be 10. Disk reference is the address of the data. M <= 228 if it is equal to 228, you have maxed out the number of children per sector Each node represents a disk block By reducing the number of steps, you reduce the amount of Disk I/O By increasing number of disk references in a node, it becomes more efficient. You can search through to find a value by doing a binary search B TREES - DELETING NODES ------------------------ Start with an already initialized B Tree Delete is physical delete, not a lazy delete *** Requirement to understand how to delete nodes on paper, not in code *** HASHING ------- building a hash table... goal is to perform inserts, deletes and finds in in constant average time implemented by an array Assume table (array) size is N Function f(x) maps any key x to an int between 0 to N-1 N=15 0