Grokking the System Design Interview

0% completed

​

Indexes

Indexes are well known when it comes to databases. Sooner or later there comes a time when database performance is no longer satisfactory. One of the very first things you should turn to when that happens is database indexing.

The goal of creating an index on a particular table in a database is to make it faster to search through the table and find the row or rows that we want. Indexes can be created using one or more columns of a database table, providing the basis for both rapid random lookups and efficient access of ordered records.

.....

.....

.....

Like the course? Get enrolled and start learning!
Marc Schlossberg

Marc Schlossberg

· 6 months ago

I went on a small rabbit hole on how these work under the hood and it's pretty cool! So I thought I would share.

The real magic of the index is pre-sorting db pointers into a balanced binary tree.

Why SORTED?

Binary search algorithm is insanely efficient and is only possible on a sorted list. At most it will take 20 steps to return a result from a dataset of 1 million. At 10 million the max steps grows to 24. That's the power of an O(log n) function. Compare that to just iterating over 1 or 10 million records and the performance gain is apparent and significant. The obvious downside, especially in the context of solving algorithmic problems in isolation a la LeetCode, is how inefficient sorting is. That's why the pre-sorting part is so critical. But of course, to maintai

C

chosunone

· 4 months ago

This is extremely weak, essentially a stub to "go look at the wikipedia page for indexes". This course should mention how indexes work, such as multiple column indexes and when you should or shouldn't expect an index to improve performance.

A

Andrew Horn

· 4 years ago

Silence broken!

N

Noam Ou

· 4 years ago

How do I practice what I'm learning?