Database Indexes

B-Tree Index

B+Tree Index

LSM Tree Index

• Red-black tree, balanced binary tree, etc
• WAL for memtable