After mentioning LSMTrees, BTrees, Rtrees, 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: https://excalidraw.com/#json=z6OfXNuA...
screenshots of the excalidraw file: https://imgur.com/a/C37N2hh
text files:
overview.md https://pastebin.com/HgmV8dRi
indexing.md https://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 KV Stores
14:32 BTrees vs. LSMTrees
20:33 Secondary Indexes
24:15 Local Secondary vs. Global Secondary
29:02 MultiDimensional Indexes
29:37 Concatenated Indexes
31:52 RTrees vs. QuadTrees vs. GeoHashes
37:33 Inverted Indexes
42:15 Skip Lists
44:20 Vector Indexes
48:42 Data Cubes & Materialized Views
50:56 CountMin Sketch
#systemdesign #programming