Absolutely Everything That I Know About Database Indexes

After mentioning LSM-Trees, B-Trees, R-trees, etc. in passing for over a year in my system design videos, I've received enough requests to make an entire video about it that I finally caved and decided to make another system concepts video.

NOTES & CORRECTIONS:
excalidraw file: excalidraw.com/#json=z6OfXNuA1htMbSEfXeixq,8-DMBtQ…
screenshots of the excalidraw file: imgur.com/a/C37N2hh
text files:
overview.md - pastebin.com/HgmV8dRi
indexing.md - pastebin.com/KtuELqhJ
the excalidraw link and screenshots above contain the corrected version of the drawing for the "write heavy" scenario

00:00 Intro
00:45 Resources & References
01:26 Key Concepts
01:36 Key Concept: RUM Conjecture
03:08 Key Concept: DB = WAL + Materialized View
03:50 No Index
06:45 Primary Keys
08:56 Partitioning Strategies: Hash Partitioning vs. Range Partitioning
11:52 K-V Stores
14:32 B-Trees vs. LSM-Trees
20:33 Secondary Indexes
24:15 Local Secondary vs. Global Secondary
29:02 Multi-Dimensional Indexes
29:37 Concatenated Indexes
31:52 R-Trees vs. Quad-Trees vs. Geo-Hashes
37:33 Inverted Indexes
42:15 Skip Lists
44:20 Vector Indexes
48:42 Data Cubes & Materialized Views
50:56 Count-Min Sketch

#systemdesign #programming