ISAM Indexed SequentialAccess Method Adapted from Prof Joe Hellerstein s notes http db cs berkeley edu dbcourse notes html A Note of Caution ISAM is an old fashioned idea B trees are usually better as we ll see Though not always But it s a good place to start Simpler than B tree but many of the same ideas Upshot Don t brag about being an ISAM expert on your resume Do understand how they work and tradeoffs with B trees Range Searches Find all students with gpa 3 0 If data is in sorted file do binary search to find first such student then scan to find others Cost of binary search can be quite high Simple idea Create an index file Level of indirection again Page 1 Page 2 Index File kN k1 k2 Page 3 Page N Data File Can do binary search on smaller index file index entry ISAM P 0 K 1 P 1 K 2 P K m 2 Index file may still be quite large But we can apply the idea repeatedly Non leaf Pages Leaf Pages Overflow page Leaf pages contain data entries Primary pages Pm Example ISAM Tree Each node can hold 2 entries no need for next leaf page pointers Why Root 40 10 15 20 33 20 27 51 33 37 40 46 51 63 55 63 97 Data Pages Comments on ISAM Index Pages File creation Leaf data pages allocated Overflow pages sequentially sorted by search key Then index pages allocated Then space for overflow pages Index entries search key value page id they direct search for data entries which are in leaf pages Search Start at root use key comparisons to go to leaf Cost log F N F entries index pg N leaf pgs Find leaf where data entry belongs put it there Insert Could be on an overflow page Delete Find and remove from leaf if empty overflow page de allocate atic tree structure inserts deletes affect only leaf pages Example ISAM Tree Each node can hold 2 entries no need for next leaf page pointers Why Root 40 10 15 20 33 20 27 51 33 37 40 46 51 63 55 63 97 After Inserting 23 48 41 42 Root 40 Index Pages 20 33 20 27 51 63 51 55 Primary Leaf 10 15 33 37 40 46 48 41 Pages Overflow 23 Pages 42 63 97 then Deleting 42 51 97 Root 40 20 10 15 20 27 23 51 63 33 33 37 40 46 55 63 48 41 Note that 51 appears in index levels but 51 not in leaf
View Full Document
Unlocking...