تا حالا دیتابیس را جعبهای میدانستیم که کوئری میخورد و جواب میدهد. اما انتخاب بین «نوشتن-سریع» و «خواندن-سریع» از خودِ موتور ذخیرهسازی میآید: B+Tree (قلب Postgres و InnoDB) درجا بهروزرسانی میکند و برای خواندن بازهای عالی است؛ LSM-Tree (قلب Cassandra ،RocksDB و LevelDB) همهچیز را append میکند و برای نوشتن سنگین ساخته شده است.
B+Tree: صفحات مرتب، بهروزرسانی درجا
- داده در صفحات (Page) مرتبِ معمولاً 4KB تا 16KB نگه داشته میشود؛ درختِ کمعمق (۳-۴ سطح برای میلیاردها سطر) جستجو را به چند خواندن دیسک میرساند.
- UPDATE یعنی یافتن صفحه و تغییر همانجا؛ اگر صفحه پر شود، split لازم است — نوشتن تصادفی روی دیسک.
- قبل از نوشتن روی صفحه، تغییر در WAL (Write-Ahead Log) ذخیره میشود تا crash داده را نبرد: اول لاگ، بعد صفحه.
- خواندن بازهای (BETWEEN ،ORDER BY) بهخاطر ترتیب فیزیکی صفحات بسیار ارزان است.
LSM-Tree: هیچچیز را درجا عوض نکن
DIAGRAMمسیر نوشتن در LSM
Write
→
WAL — دوام
→
Memtable — RAM مرتب
→
Flush → SSTable غیرقابلتغییر
→
Compaction
- نوشتن فقط به WAL + یک ساختار مرتب در RAM (Memtable) است — به همین دلیل نوشتن وحشتناک سریع است؛ همهچیز sequential.
- وقتی Memtable پر شد، بهصورت SSTable غیرقابلتغییر روی دیسک ریخته میشود؛ UPDATE و DELETE هم فقط رکورد جدید (با tombstone) هستند.
- خواندن باید Memtable و چند SSTable را بگردد — به همین دلیل LSM کنار هر SSTable از Bloom Filter (فصل ۱۰) استفاده میکند تا سراغ فایل بیربط نرود.
- Compaction پسزمینه SSTable ها را ادغام و نسخههای قدیمی را دور میریزد؛ دو سبک: Size-Tiered (نوشتنمحور) و Leveled (خواندنمحور).
تقابل اصلی: چه چیزی را میدهی، چه میگیری
| B+Tree | LSM-Tree | |
|---|---|---|
| مدل | بهروزرسانی درجا | Append-only + ادغام پسزمینه |
| نوشتن | تصادفی روی دیسک؛ کندتر در نوشتن سنگین | Sequential؛ چند برابر سریعتر |
| خواندن بازهای | عالی — ترتیب فیزیکی حفظ است | باید چند فایل merge شود؛ کندتر |
| فضا | پراکندگی صفحات (fragmentation) | Write amplification در compaction؛ نیازمند فضای موقت |
| نمونه | PostgreSQL ،MySQL (InnoDB) | Cassandra ،RocksDB ،LevelDB ،ScyllaDB |
به زبان ساده
دیتابیسها دو مکتب ذخیرهسازی دارند: B+Tree برای خواندن سریعِ تکرکوردی و LSM برای نوشتن سیلابی؛ انتخاب موتور یعنی انتخاب همین مصالحه.
مثال واقعی
دفتر حسابداری B+Tree مثل کارتابل مرتب است که سریع هر نام را پیدا میکنی؛ LSM مثل دفترچه یادداشت روزانه است که سریع آخرش مینویسی و آخر هفته مرتبش میکنی.