In order to ask my question I first need to explain my understanding of both concepts.
Actually, my understanding is very vague, so stop me if I’m wrong.
Index (btree in SQL):
An index is helpful for relational databases to speed up queries.
For instance, let’s take a customer table and index it on the age column.
It will build a binary tree where each node has such structure [age, addresses of corresponding records].
Let’s consider this filter WHERE AGE=18, then if the database holds N records and M different values for the indexed column, you can achieve this query in O(log(M)) (binary search) rather than O(N)
HashMap:
Then, I came across hashmap, where lookup is O(1) ? hum!! interesting!!
If key, value is one of the entry, it will encode the key so that it becomes a hash and hold it as its key. Also holds the address of the value as value.
When you lookup for a key, it encodes it, hence finds the hash. Then it knows where to find the hash as the hash is actually some kind of an address itself (base + index * stride). Hence, get the actual address of that value and go fetch the value itself.
Question:
Why don’t SQL databases use hashmap for unique keys and get better performances?
Advertisement
Answer
Hashmaps can only be used for equality queries. Hence, they are not generally useful. A b-tree index on (x) can be used for queries like this:
select max(x) from t select count(*) from t where x between 1 and 10
Multi-column hashmaps cannot (in general) access each key individually. So, the above queries could use a b-tree index on (x, y) as well as on on (x).
In addition, logarithms are pretty small. It can be hard to tell the difference between O(log n) and O(1) on the small numbers we deal with in databases.
And, hashmaps are not quite so O(1) as they scale. Eventually, they start having collisions and will be larger than memory — both of which can have a significant impact on performance.