Merge Sort, Arrays, Trees, Hash Tables and Your Relational Database

While recently browsing the Interwebs, I came across this very interesting article about how relational databases work.

Now, being somewhat of a database geek (I’ve so far managed to make a career out of working with databases in an age where all my former classmates are, in one way or another, working with web applications) I was instantly intrigued. I was even more so when I discovered that this wasn’t just your run of the mill article about entities, relationships between tables, foreign keys and normalization. Rather, this is an article about the seedy underbelly of relational databases that some of my developer colleagues would never admit to existing.

What this article reminded me was that:

1. All the stuff I learnt about time complexity in college was not a waste of time.

2. A simple merge sort algorithm can be twisted and turned in order to yield the best time, the best size, best I/O count or best distributed query, according to one’s needs.

3. Two dimensional arrays are the easiest way to imagine a table. Also, they suck when it comes to finding information in them.

4. I hate binary search trees, but once you get the hang of them, they prove to be amazingly useful. Also, they’re the best way to explain database indexes.

5. With a good Hash function your search time is O(1).

And there’s more to come :).


Published by


I may be late due to who I am as a person