Indexing

Introduction

A Database Index, similar to hashmap lookups increases Database READ operations. The index data structure makes this possible through several implementations.

Types of Database Index

1. 1. Primary Index: Indexing on the primary key of a DB table
2. 2. Secondary Index: Index based on a candidate key - a set of columns, but not a single column key
3. 3. Clustering Index: Indexing to a block of data. The index points to a block of data containing DB rows and not directly to a row of data
4. 4. Dense index: A 1-to-1 mapping that points directly to their data block
5. 5. Spare index: points to a data block/row then starts searching for the desired DB row in a linear fashion 1-by-1
6. 6. Hash index: Utilizing a hash function to map an input key to a memory address corresponding to a block of data. Resolving Duplicate keys adds overhead to this approach

B-Tree

B-Tree's or B+Tree is the general data structure used to implement the database index data structure. Both data structures are reminiscent of a binary tree. The two implementations differ because B-Tree stores data at every leaf node and a B+Tree stores data only at child nodes. To keep it simple these implementations support log(n) data operations for inserts, deletes, updates; this makes it optimal for databases.

A B+Tree will also normally connect its children sequentially - an array of child nodes if you may. The B+Tree can Binary Search or sequential access child nodes depending on the needs. A B+Tree stores DB rows, where the child nodes are DB rows.

A B-Tree only provides indexing functionality because it should be quick. Also, this tree generates at index creation, not before; saving space. The B-Tree is only for the index search. Compared to a B+Tree the primary difference is a B-Tree will only operate on the index while a B+Tree can search for any column value.

Advantages of database indexing

Indexing increases the READ speed from a Database system.

The data access size should be small in order to sufficiently optimize this access (a few KB at most).

Disadvantages of database indexing

While DB indexing increases READ speed there are several tradeoffs to be aware of:

1. 1. Index only benefits READ heavy systems, if the system is WRITE heavy the index won't help
2. 2. An Index requires more memory and compute power
3. 3. Data requires a unique, primary key
4. 4. Older DB's may not allow indexes and partitions
5. 5. Other operations (ie INSERT, DELETE, UPDATE) have reduced performance because they have to operate on an index now performance degrades when adding more than one index

Conclusion

Database indexing exists as a powerful resource, but also a potential burden. Indexes can speed up database queries to benefit the caller; improper use of index however can result in system degradation. Before applying this optimization determine whether the system will benefit from faster READ operations at the tradeoff of higher memory usage.