Database — Different kinds of Index
When you want to look up a word in the dictionary, you could use index page to find it out quickly. Database index is same idea, you can use it to make your SQL query run efficiently.
Clustered Index vs Non-clustered Index
The clustered index defines how the data be organized in the disk, in other words, the leaf nodes of the clustered index contains real data blocks. The data in the disk can be stored in only one way, so there could be only one clustered index for each table. For MySQL database, it will create the clustered index by the primary keys by default. The SELECT SQL will return the data following the order of the clustered index if you don’t specify other ORDER BY condition.
The Non-clustered index only store the pointer in the leaf node which point to the real data block. Therefore, you could create multiple non-clustered indexes based on your use cases. The non-clustered index is also called secondary index.
B-Tree Index vs Hash Index
Compare to traversing all records, using tree-based index could reduce the time complexity of the search process from O(n) to O(logn) on average. A B-tree index could be used for the =, >, >=, <, <=, or BETWEEN operators.
There is another option to build the index into a hash table structure which could reduce the time complexity to even O(1) on average. However, such index could only be used for the = or <=> operators. Also, it could not used to speed up the ORDER BY operation.
Since we can have one clustered index with multiple non-clustered indexes for a table. How we can make sure the database will used the proper one? Let me introduce that part in the next post.
