Table of Contents
Indexing
Topics
Terms and Distinctions
Dense and Sparse Primary Indexes
Multi-Level Indexes
A Note on Pointers
Representation of Duplicate Values in Primary Indexes
Deletion from Dense Index
Deletion from Sparse Index
Deletion from Sparse Index (cont’d)
Deletion from Sparse Index (cont’d)
Insertion in Sparse Index
Secondary Indexes
Duplicate Values and Secondary Indexes
PPT Slide
Advantage of Buckets: Process Queries Using Pointers Only
Buckets and Pointers Operation Used in Information Retrieval
Summary of Indexing So Far
B+ and B-Tree Indexes
Properties of B+-trees
Lookup Algorithm
Insertion Algorithm
Insertion Algorithm: Splitting Nodes
Insertion: Splitting Recursively
Insertion: Splitting Recursively
Deletion: The No-Combining Pages Case
PPT Slide
Deletion: The Case for Transferring Items From Siblings
PPT Slide
Deletion: Reducing Levels
The B-Tree Variant: B+-Tree Remains the Winner
Comparison: Static (Conventional) Indexes Vs B+Trees
An Interesting Problem
Hashing
How do we choose a hashing function ?
How Many Buckets ?
Extensible Hashing
Extensible Hashing Example
Extensible Hashing Example (cont’d)
Indexing vs Hashing
Comparison of Index Methods
Multi-Key Indexing
PPT Slide
Solution 3: Multi-Key Indexing
Common Applications of Multi-Key Indexing
Grid Structure
|