Index Evaluation Metrics
- Access types: The types of access that are supported efficiently. Access types can include finding records with a specified attribute value and finding records whose attribute values fall in a specified range.
- Access time: The time it takes to find a particular data item, or set of items, using the technique in question.
- Insertion time: The time it takes to insert a new data item. This value includes the time it takes to find the correct place to insert the new data item, as well as the time it takes to update the index structure.
- Deletion time: The time it takes to delete a data item. This value includes the time it takes to find the item to be deleted, as well as the time it takes to update the index structure.
- Space overhead: The additional space occupied by an index structure. Provided that the amount of additional space is moderate, it is usually worthwhile to sacrifice the space to achieve improved performance.
Why we need Multi-level indexing
B Tree
5 Database Management System - File Organization & Indexing, p.14
5 Database Management System - File Organization & Indexing, p.15
B+ Tree
5 Database Management System - File Organization & Indexing, p.27