DBMS - File Indexing Flashcards
Index Structure
Data Structure and associated set of operations whose goal is the effective retrieval of data based on a criterion matched to part of the data file
Example of index Structures
BTree, Extensible Hashing, Bit mapped
Example of search key
Empno, deptno, sal
Indexed key
not necessarily the primary key set or the foreign key
Index File
The reordering of part of a data file’s record to facilitate certain retrieval patterns.
Composed of many pairs of search key values and data file record pointers to the respective record with that matching value in the data file.
Index building and maintenance activities
needed to maintain its currency
Index retrieval
usually meant to return an address in the data file where key matches criteria
Index range scan
Oracle reads root node of index and block in each branch level. Leaf blocks scanned until the end of the range is encountered.
Two index modality of interest
Indices with ordered search keys, indices with search keys hashed
Clustered Index
Index with its search key specified on the ordering field of a sequential file of records.
Search key could be PK, if it is we have an index-sequential file.
Non-Clustered Index
An index on the ordering field of an ordered file of records.
Can either have primary or clustering type index but not both.
Secondary Index
Can be specified on any non ordering field of a data file. Doesn’t interfere with primary or clustered indexes.
Index Density
The ratio of search keys to records in the data. If >=1 it is dense.
Multilevel indexing
Indexes of indexes
Why Indexing?
- Max access speeds
- Min access costs
- sequential traversal of data
- constraints for query, semantic and security
Index Computational Costs
- Time
- Space
- Resilience
- Concurrency Support
Index Issues
- Each index structure comes with a respective set of retrieval operators
- Excessive use of indexes deteriorates and floods disk IO bandwidth
- Concurrency Control Issues
- Indexes created and maintained but never used
- Index use vs Sequential Scan
Pin the address to an actual memory/file location
as late as possible
Covering Indexes
When index entry contains the data record too
Delete in a PK index
Search key in index, get record in data file, delete and reorganize data file
Delete in a data file with a primary index
Get record in data file, search key in each primary index, delete index entry and reorganize each primary index
Delete in a non-clustered index (By search index entry)
Get record in data file, get index entry.
IF data file has 1 search key instance, delete data file+index entry+ reorganize both
ELSE delete data file record and reorganize data file
Delete in a non-clustered index (By RRN entry)
Search key in index, get first record in data file, DO delete and reorganize data file, WHILE next RRN has same key. Delete index entry and reorganize
Sorting Datafiles Requirement
- If data fits into main memory use Quicksort
- If it doesnt fit into main memory use external merge sort
- Can use indexes to help sort
Sorting Requirements
ORDER BY or SELECT DISTINCT
In data cursors that is processing some subset of a table in main memory, one can sort it or leave it unordered.