Grokking the System Design Interview
Vote

0% completed

​

Indexes

A database can find rows in two ways.

It can read every row in the table and check each one. This is called a full table scan. With a million rows, the database reads a million rows to find one.

Or it can look in an index. An index is a separate structure that holds the values of one or more columns in sorted order. Next to each value is a pointer to the row it came from.

A library catalog is the same idea. The catalog is a sorted list of titles, and next to each title is the shelf number. You do not walk along every shelf

.....

.....

.....

Like the course? Get enrolled and start learning!
C

chosunone

· 5 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.

Marc Schlossberg

Marc Schlossberg

· 8 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

N

Noam Ou

· 4 years ago

How do I practice what I'm learning?

A

Andrew Horn

· 4 years ago

Silence broken!

Reading Progress

0%