Understanding ISAM Indexes and Tree-Structured Indexing Techniques
This content delves into the concepts of ISAM (Indexed Sequential Access Method) indexes and tree-structured indexing techniques used in database management. It explores the differences between ISAM and B+ trees, the implementation of sparse and dense indexes, and the structure of ISAM tree indexes. The content also covers range searches, static index creation in ISAM, and the advantages and trade-offs associated with different indexing methods.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
ISAM Indexes Credits: Franklin Textbook to be published by Pearson Ed in early 2014 CSCIX370: Database Management http://www.funwebdev.com
How to Build Tree-Structured Indexes Tree-structured indexing techniques support both range searches and equality searches. Two examples: ISAM: static structure; early index technology. B+ tree: dynamic, adjusts gracefully under inserts and deletes. CSCIX370: Database Management
ISAM = Indexed Sequential Access Method 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 Do understand how they work, and tradeoffs with B+ trees CSCIX370: Database Management
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 on disk is still quite high, so use a Single Level Index Index File kN k2 k1 Data File Page N Page 3 Page 1 Page 2 CSCIX370: Database Management
ISAM Typically a Sparse Index Sparse: key k_i references a block/page Dense: key k_i references a record/tuple A Sparse Index is usually small and likely to fit in main memory Index File kN k2 k1 Data File Page N Page 3 Page 1 Page 2 * Can do binary search on index file! CSCIX370: Database Management
index entry ISAM P0 K1 Pm P1 K2 P2 Km We can apply the idea repeatedly! Non-leaf Pages Leaf Pages Overflow page Primary pages CSCIX370: Database Management
Example ISAM Tree Index entries:<search key value, page id> they direct search for data entries in leaves. Example where each node can hold 2 entries; 40 Root 51 63 20 33 46* 55* 40* 51* 97* 10* 15* 20* 27* 33* 37* 63* CSCIX370: Database Management
ISAM has a STATIC Index Structure File creation: 1. Allocate leaf (data) pages sequentially 2. Sort records by search key 3. Allocate index pages 4. Allocate overflow pages Data Pages Index Pages Overflow pages ISAM File Layout Static tree structure: inserts/deletes affect only leaf pages CSCIX370: Database Management
ISAM (continued) Data Pages Index Pages Search: Start at root; use key comparisons to navigate to leaf. Cost = log F N F = # entries/pg (i.e., fanout) N = # leaf pgs no need for `next-leaf-page pointers. (Why?) Overflow pages Insert: Find leaf that data entry belongs to, and put it there. Overflow page if necessary. Delete: Find; remove from leaf; if empty de-allocate. CSCIX370: Database Management
Example: Insert 23*, 48*, 41*, 42* Root 40 Index Pages 51 63 20 33 Primary Leaf 46* 55* 40* 51* 97* 10* 15* 20* 27* 33* 37* 63* Pages 41* 48* 23* Overflow Pages 42* CSCIX370: Database Management
... then Deleting 42*, 51*, 97* Root 40 Index Pages 51 63 20 33 Primary Leaf 46* 55* 40* 51* 97* 10* 15* 20* 27* 33* 37* 63* Pages 41* 48* 23* Overflow Pages 42* * Note that 51* appears in index levels, but not in leaf! CSCIX370: Database Management
ISAM ---- Issues? Pros ???? Cons ???? CSCIX370: Database Management
