· · ─ ·✶· ─ · ·
Databases. They’re used everywhere on the internet. When we search something on Google or YouTube. When we shop online on Amazon or eBay. Ever wondered how these things can trawl through millions of records and give us back results under milliseconds? Ever wondered “How do databases find things fast?”
Recently I’ve been fascinated with them, pushing me to go past select * from employee;. To peel back the hood and understand what going on underneath… to an extent. Instead of picking up a book about databases and going through it, I figured I’d try something different, something that aligns more closely to way I think and learn. Which is by reasoning from first principles and engaging in a Socratic dialogue (typically with myself but preferably with someone who knows more about a certain topic). Hmm, whom can I bother to be painstakingly patient with me as I reason this out? Whom else other than Claude Sonnet 5 (well, I don’t have the tokens to ask Claude Fable). So this post is an abridged version of the Socratic dialogue I engaged with Claude in order to reason out the answer from first principles. This is a very effective approach to learn, especially using LLM’s without just having the LLM give you the answer.
That said, this isn’t a complete picture of everything involved in how databases search and retrieve data fast but it follows a single thread and tries to reason toward an answer from first principles.
TL;DR: Figure out how databases find things fast using Socratic dialogue with Claude.
To kick things off, let’s define our objective more specifically. As an example lets say, we have a bunch of rows with the column age and we’re running select * from <table> where age=30 query. Naturally, we want the results fast. If we we’re to iterate over all the rows, match and retrieve based on the age value, we’d be here for minutes. And we can’t have that, not in this attention economy. So to speed things up, we’ll be basically creating a database index for the age column. What’s a database index? A database index is like a yellow pages directory. For each possible value of age in our table, it links to the actual row on the hard disk (or wherever the actual row data is stored). So a O(1) way of doing this is to use a hashtable. But what’s the underlying data structure for the hashtable? The simplest one would be to use an array. We compute the hash from the age value (30 in our example) and use that as the index of the array into which we insert the appropriate row(s). Here 30 is the key and the row(s) associated with 30 is the value with regards to a typical key-value pair in a hashmap.
But complications due to key collisions arise when we use a simple array our our backing data structure. Key collision is a scenario where we want to insert a row with an age that coincidentally happens to have the same hash as another different age. The below code demonstrates this issue (a famous example in Java):
System.out.println("Ea".hashCode()); // Prints 2236
System.out.println("FB".hashCode()); // Prints 2236If we replace the old value with the new value (associated with a particular key), then we are effectively losing the old data. In terms of our example, this would mean that we originally had a row with age 30 and then a new row with a different age value just replaced the old one. Not good.
There are two ways to solve key collisions.
First is chaining. Simple enough, when a key collision occurs we append the new value to the old value. And what’s a data structure that allows us to do this? Linked lists. Why not just use an array again? Because we would never know the size of this inner array before hand. Linked lists increase in size only when required. So what does this look like? We have an array and all the elements of this array are references to the head of a linked list.
The other way to solve key collisions in a hashtable is called open addressing. Essentially, here we don’t save the new value and the old value in the same array location but instead we smartly store the new value “near” the location of the old value.
So this approach of implementing a hashtable with an array + linked list is great. Great for direct matches but not ranged queries. And now we have unlocked the next puzzle. Ranged queries. Suppose we want to do select * from <table> where age < 30. We might think the approach here would be to compute the hash of 30, use that as the index in the array and return back every item from the array less than or equal to that index. But thats not correct. When we compute hash, it scatters the keys to store them across the entire array by design. So a hash for 30 might give us the index 4 but hash for 31 would not be 5, it could be 1. The hash function is not monotonically increasing. So using an array as the backing data structure for our hashtable does not guarantee ranged queries to work properly.
· · ─ ·✶· ─ · ·