Indexing in Database
Indexing is a technique used in a database to make the retrieval of records faster and more efficient. DBMS uses an index to locate the required records without scanning the entire data file.
- Indexing improves database performance by minimizing the number of disc visits required to fulfill a query.
- It is a data structure technique used to locate and quickly access data in databases.
- Indexing in database is used to reduce the I/O cost. The number of blocks transferred from secondary memory to primary memory is called I/O cost.
Ordered Index
An ordered index is an index in which the index entries are maintained in sorted order according to the search-key values.
Ordered indexes are particularly useful when we need to perform range searches, such as finding all students whose roll numbers are between 100 and 120.
Primary Index
A primary index is an index created on a file that is physically ordered according to its primary key or ordering key.
- DB file should be physically ordered based on search key used in the index file.
- Search key should be Primary Key or Alternative Key for DB file.
Suppose student records are stored according to Roll_No. as 101, 105, 110, 115, 120, 125.
If the file is physically arranged according to Roll_No, an index created on Roll_No is called a Primary Index.
Primary Index : Ordering Key : Usually Sparse
Clustering Index
A clustering index is an index used when the records in a file are physically ordered according to a non-key attribute, called the clustering field.
- A non-key attribute can contain duplicate values.
For example, consider employee records arranged according to Department:
| Employee | Department |
|---|---|
| E1 | HR |
| E2 | HR |
| E3 | IT |
| E4 | IT |
| E5 | Sales |
| E6 | Sales |
Here, Department is a non-key attribute because several employees can have the same department. A clustering index can point to the beginning of each group:
| Department | Pointer |
|---|---|
| HR | HR Group |
| IT | IT Group |
| Sales | Sales Group |
Thus, instead of identifying a single record, the index helps locate a group of records having the same clustering-field value.
Secondary Index
A secondary index is an index created on a search key that does not determine the physical ordering of the data file.
Suppose a student file is physically arranged according to Roll_No as 101, 102, 103, 104, 105, ...
Now suppose we frequently search students by their Name. An index can be created on Name, even though the actual data file is not physically ordered by Name. That index is called a Secondary Index.
- A secondary index is generally Dense Index, because the search key is not the ordering field of the data file.
- Secondary Index : Non-ordering Search Key : Usually Dense
- We can build more than one secondary index according to requirement.
- In multi-level indexing, except first level, all other level of index is generally sparse.
Sparse Index
A sparse index contains index entries for only some search-key values. In the classical primary-index arrangement, there is commonly one index entry for each data block.
| Index Key | Pointer |
|---|---|
| 101 | Block 1 |
| 115 | Block 2 |
| 130 | Block 3 |
A sparse index requires less storage than a dense index. After locating the appropriate block through the index, the DBMS may search within that block to find the required record.
Dense Index
A dense index contains an index entry for every search-key value or, in the common record-level case, an entry for every record.
| Index Key | Pointer |
|---|---|
| 101 | Record 1 |
| 105 | Record 2 |
| 110 | Record 3 |
| 115 | Record 4 |
The main advantage of a dense index is that it can provide direct and fast access to records. The disadvantage is that it requires more storage space and more maintenance when records change.
Dense Index vs Sparse Index
| Feature | Dense Index | Sparse Index |
|---|---|---|
| Number of Entries | More | Fewer |
| Storage Requirement | Higher | Lower |
| Entry for every record/search-key value | Yes | No |
| Search within Data Block | Usually less necessary | May be required |
| Classical Example | Secondary Index | Primary Index |
Hash Index
A hash index uses a hash function to determine the location of a record or bucket.
Unlike an ordered index, the entries are not maintained primarily for sequential ordering. Instead, a search-key value is passed through a hash function.
- Hash indexing is particularly efficient for exact-match.
Static Hashing
In static hashing, the number of buckets is fixed when the hash structure is created.
Dynamic Hashing
In dynamic hashing, the hash structure can grow or adapt as the number of records changes.
This is useful for databases where records are frequently inserted or deleted. Instead of keeping a permanently fixed number of buckets, the structure can be adjusted as required.
Two important dynamic hashing techniques are, Extendible Hashing and Linear Hashing.
Summary of Types of Indexing
| Category | Type | Short Description (Summary) |
|---|---|---|
| Ordered Index | Primary Index | Created on the ordering key of a sequentially ordered file. Generally Sparse. |
| Clustering Index | Created on a non-key field according to which the file is physically ordered. | |
| Secondary Index | Created on a search key that does not determine the physical ordering of the file. Generally Dense. | |
| Index Density | Dense Index | Contains an index entry for every search-key value/record, depending on the specific organization. |
| Sparse Index | Contains entries for only some search-key values, commonly one per data block in a primary index. | |
| Hash Index | Static Hashing | Uses a fixed number of buckets. |
| Dynamic Hashing | Allows the hash structure to grow or adapt as data changes. | |
| Dynamic Hashing | Extendible Hashing | Uses a directory and dynamically splits buckets. |
| Linear Hashing | Uses gradual, progressive bucket splitting to grow the file. |
- Primary Index : Ordering key : Usually Sparse
- Clustering Index : Non-key ordering field
- Secondary Index : Non-ordering search key : Usually Dense
- Dense Index : Entry for every search-key value/record
- Sparse Index : Entries for only some search-key values
- Static Hashing : Fixed number of buckets
- Dynamic Hashing : Hash structure can grow or adapt
- Extendible Hashing : Directory + dynamic bucket splitting
- Linear Hashing : Gradual, progressive bucket splitting
