Indexes are the fundamental unit of database performance. There are many index types, but the two most common are the B+ Tree and the hash index.
B+ trees are the default index type for most database systems and are more flexible than hash indexes. They offer excellent lookup and insertion times when configured correctly, and my personal opinion is that you should stick with B+ trees unless you're trying to optimize an extremely performance sensitive table.
For example, later on, I will show that it only takes 4 disk I/Os to find a value in 8 TB of data using a properly configured B+ tree. No, that's not a typo. Unless you absolutely need to save 3 disk I/Os, then you should preserve the flexibility of a B+ tree.
Let’s start by introducing the B+ tree and hash index.
A B+ Tree is a tree data structure with some interesting characteristics that make it great for fast lookups with relatively few disk IOs.
A hash index takes the key of the value that you are indexing and hashes it into buckets. In case you’re not aware, a hash function is something that takes an input, and produces a different, somewhat random, and hopefully unique, output.
If you are 100% certain that a column will only ever need to be looked up via direct equality (eg... where id = X), then you can use a hash index. Even in that case, unless that table is at the core of your business and is becoming a bottleneck for system performance in general, I would just use a B+ tree anyways. Why? Because you're really not giving up very much!
Lookup times: log f (N/F) disk IOs, where:
Example
If you actually have DB tables where just the index is 8 TB, then you are probably at Google. Cool! Hire me! For most people however, your indexes will probably be small enough to fit in RAM, and won't require any IOs at all!
Only allows exact equality (and by extension, inequality) operators.
Lookup times: 0(1). It's hard to beat that!
I hope this article shed some light on when you should use each type of index.