SQLite Deep Dive (Part-6) — B-Tree: SQLite ရဲ့ ကျောရိုး

ကျွန်တော်တို့ SQLite ရဲ့ အတွင်းပိုင်း File Structure ကိုလည်း လေ့လာပြီးပြီ၊ Page တွေ ဘယ်လိုအလုပ်လုပ်လဲဆိုတာလည်း သိပြီ၊ Type System နဲ့ NULL တွေရဲ့ လျှို့ဝှက်ချက်ကိုလည်း နားလည်ခဲ့ကြပြီ။ Query တစ်ကြောင်းက Raw Text ကနေ Bytecode အဖြစ် ပြောင်းလဲသွားပုံကိုတောင် အသေးစိတ် ကြည့်ခဲ့ပြီးပါပြီ။ အခုတော့ အရေးကြီးဆုံးအပိုင်းကို ရောက်လာပါပြီ။ အဲဒါကတော SQLite ဟာ ဒီလောက်များပြားတဲ့ ဒေတာတွေထဲကနေ ကိုယ်လိုချင်တဲ့အချက်အလက်ကို မျက်စိတစ်မှိတ် မျက်တောင်တစ်ခတ်အတွင်း ဘယ်လိုမျိုး Search လဲဆိုတာပါပဲ။

စနစ်တကျ တည်ဆောက်ထားတဲ့ Structure မရှိဘူးဆိုရင် ဒေတာ Row တစ်သန်းဆိုတာ file ထဲမှာ အစီအစဉ်မရှိ စုပုံနေတဲ့ Data တွေသက်သက်ပါပဲ။ တကယ်လို့ ဒီလိုစုပုံနေတဲ့ Query တစ်ခုပတ်တိုင်း Full Table Scan ဖြစ်သွားပါလိမ့်မယ်။ ဆိုလိုတာက Page တိုင်းကို လိုက်ဖတ်၊ Row တိုင်းကို လိုက်စစ်နေရမှာဖြစ်လို့ Record တစ်ရာလောက်မှာ ပြဿနာမရှိပေမဲ့ Record တစ်သန်းလောက် ဖြစ်လာရင်တော့ Performance သိသိသာသာ ကျဆင်းသွားပါလိမ့်မယ်။

ဒီလို နှေးကွေးလွန်းတဲ့ အခြေအနေကနေ မျက်စိတစ်မှိတ်အတွင်း အဖြေထွက်လာအောင် ဖန်တီးပေးနိုင်တဲ့ လျှို့ဝှက်ချက်ကတော့ B-Tree ပဲ ဖြစ်ပါတယ်။

B-tree က ဘာကို ဖြေရှင်းတာလဲ?

B-tree ဆိုတာ ဘာလဲဆိုတာ အသေးစိတ် မပြောခင်မှာ သူဟာ ဘယ်လိုပြဿနာကို ဖြေရှင်းပေးနေတာလဲဆိုတာ နားလည်ထားဖို့က ပိုအရေးကြီးပါတယ်။

Table တစ်ခုမှာ Row 1,000,000 ရှိတယ်ဆိုပါစို့။ ကျွန်တော်တို့ကအောက်က Query ကို Run လိုက်တယ်-

SELECT * FROM users WHERE id = 847293;

တကယ်လို့ SQLite က Row တွေကို ဘာ Structure မှမရှိဘဲ တစ်ကြောင်းပြီးတစ်ကြောင်း သိမ်းထားတယ်ဆိုရင် id = 847293 ကို ရှာဖို့အတွက် အစကနေ တစ်ခုချင်းစီ လိုက်စစ်နေရမှာပါ။ ပျမ်းမျှအားဖြင့် Comparison ပေါင်း ငါးသိန်းကျော် လုပ်ရမှာဖြစ်လို့ Dataset ကြီးမားလာတဲ့အခါ ဒါဟာ လက်မခံနိုင်လောက်အောင် နှေးကွေးသွားပါလိမ့်မယ်။

Phonebook တစ်အုပ်ကို ပြန်မြင်ကြည့်ပါ။ ‘Williams’ ဆိုတဲ့ နာမည်ကို ရှာဖို့ စာမျက်နှာ (၁) ကနေ တစ်ဦးချင်းစီ လိုက်ဖတ်နေမှာ မဟုတ်ပါဘူး။ စာအုပ်ကို အလယ်ကနေ ဖြတ်ဖွင့်မယ်၊ ‘M’ နား ရောက်နေတာ သိရင် ရှေ့ကို ထပ်လှန်မယ်၊ ‘W’ အပိုင်း ရောက်လာပြီဆိုမှ ပိုပြီး ကျဉ်းကျဉ်းမြောင်းမြောင်း ရှာဖွေပြီး နာမည်ဆီ တည့်တည့်သွားမှာပါ။ အချက်အလက်တွေ သိန်းချီရှိနေပေမဲ့ ‘Jump’ အနည်းငယ်နဲ့တင် အဖြေကို မြန်မြန်ဆန်ဆန် ရသွားတာမျိုးပါ။

ဒါဟာ B-Tree ရဲ့ အဓိက အနှစ်သာရပါပဲ။ တစ်ကြောင်းချင်းဖတ်တဲ့ Linear Scan မဟုတ်ဘဲ Logarithmic Time နဲ့ တိတိကျကျ ညွှန်ပြပေးနိုင်တဲ့ Structure မျိုး ဖြစ်ပါတယ်။ Row တစ်သန်းရှိတဲ့ Table တစ်ခုမှာ B-Tree ဟာ Comparison ပေါင်း ၂၀ ဝန်းကျင်လောက်နဲ့တင် အဖြေရှာတွေ့နိုင်ပါတယ်။ ငါးသိန်းလုံးကို လိုက်စစ်နေစရာ မလိုတော့ပါဘူး။

ဒါဟာ သာမန်ကွာခြားမှုမျိုး မဟုတ်ဘဲ မျက်စိတစ်မှိတ်အတွင်း အဖြေထွက်လာမယ့် Instant Query နဲ့ ‘App ကြီးက ဘာလို့ ဒီလောက်လေးနေတာလဲ’ ဆိုပြီး Bug Report အတင်ခံရမယ့် Query ကြားက ကွာခြားချက်ပဲ ဖြစ်ပါတယ်။

B-Tree ဆိုတာ ဘာလဲ?

လူတော်တော်များများက “B-tree” ထဲက “B” ကို “Binary” လို့ ထင်တတ်ကြပေမဲ့ တကယ်တော့ မဟုတ်ပါဘူး။ အများဆုံး လက်ခံထားကြတဲ့ သီအိုရီအရ “B” ဟာ “Balanced” ကို ဆိုလိုတာပါ။ (ဖန်တီးသူ Bayer ကိုယ်တိုင် တရားဝင် အတည်ပြုမသွားခဲ့ပေမဲ့ အရေးကြီးဆုံးအချက်ကတော့ ဒီ “Balanced” ဖြစ်နေတဲ့ အပိုင်းပါပဲ။)

ဒီနေရာမှာ “Balanced” ဖြစ်နေတာက အဓိကအချက်ပါပဲ။ ဘယ် Leaf Node ဆီကိုပဲ သွားသွား Root ကနေ သွားရမယ့် Distance ဟာ အမြဲတမ်း တူညီနေတာကို ဆိုလိုတာ ဖြစ်ပါတယ်။

B-tree ဟာ သူ့အလိုလို Balance ဖြစ်အောင် ထိန်းညှိပေးတဲ့ (Self-balancing) Tree Structure တစ်ခုဖြစ်ပြီး သူ့မှာ ထူးခြားတဲ့ လက္ခဏာ (၄) ခု ရှိပါတယ် -

1. Node တစ်ခုမှာ Key အများအပြား ရှိနိုင်ခြင်း: Binary Tree တွေလို နှစ်ခုတည်း မဟုတ်ဘဲ Key ပေါင်းများစွာကို Node တစ်ခုထဲမှာ စုစည်းထားနိုင်ပါတယ်။
2. နေရာလွတ် အချိုးအစားကို ထိန်းသိမ်းခြင်း: Root ကလွဲရင် Node တိုင်းဟာ အနည်းဆုံး တစ်ဝက် (50%) ခန့် အမြဲတမ်း ပြည့်နေရပါတယ်။
3. Depth တူညီခြင်း: Leaf Node အားလုံးဟာ တူညီတဲ့ Level (Depth) မှာပဲ ရှိနေကြတဲ့အတွက် ရှာဖွေရတဲ့ Speed က အမြဲတမ်း တည်ငြိမ်နေပါတယ်။
4. Key တွေကို Sort လုပ်ထားခြင်း: Node တစ်ခုချင်းစီထဲက Key တွေကို အစဉ်လိုက် စီထားပါတယ်။

ဒီနောက်ဆုံးအချက်ဟာ အလွန်အရေးကြီးပါတယ်။ အဆင့်တိုင်းမှာ Key တွေကို Sort လုပ်ထားတဲ့အတွက် SQLite ဟာ အဆင့်တိုင်းမှာ ဘယ်ဘက်ကို ဆက်သွားရမလဲဆိုတာ တိတိကျကျ သိနေပါတယ်။ ခန့်မှန်းနေစရာ မလိုသလို၊ လမ်းမှားသွားလို့ နောက်ပြန်လှည့်ရတာမျိုး (Backtracking) လည်း မရှိပါဘူး။

SQLite ရဲ့ Version: B+Tree

SQLite ဟာ Plain B-tree ကို မသုံးပါဘူး။ သူ့ထက် အားသာချက်ပိုများတဲ့ B+tree ဆိုတဲ့ Variant ကို သုံးပါတယ်။ သူတို့နှစ်ခုကြားက အဓိကကွာခြားချက်ကတော့ Actual Data (Row Payload) တွေကို အောက်ဆုံးက Leaf Nodes တွေမှာပဲ သိမ်းဆည်းတာ ဖြစ်ပါတယ်။ အပေါ်က Interior Nodes တွေကတော့ လမ်းညွှန် (Navigation) အတွက် Key တွေသက်သက်ပဲ ကိုင်ထားပါတယ်။

ဒီကွာခြားချက်ဟာ လက်တွေ့မှာ အကျိုးသက်ရောက်မှု အကြီးကြီးရှိပါတယ်။

Plain B-tree မှာဆိုရင် Tree ရဲ့ အလယ်ပိုင်း (Interior Node) မှာတင် ရှာနေတဲ့ Row Data ကို တွေ့ပြီး လုပ်ငန်းစဉ် ပြီးဆုံးသွားနိုင်ပါတယ်။ B+tree မှာတော့ Actual Data ကို ရဖို့အတွက် အောက်ဆုံးက Leaf Node ဆီကို အမြဲတမ်း ရောက်အောင်သွားရပါတယ်။ ဒါဟာ ပိုပြီး အလုပ်ရှုပ်တယ်လို့ ထင်ရနိုင်ပေမဲ့ အကျိုးကျေးဇူးကတော့ ပိုကြီးမားပါတယ်-

1. Tree ပိုတိုသွားခြင်း: Interior Node တွေမှာ Data Payload တွေ မကိုင်ထားတော့တဲ့အတွက် Page တစ်ခုတည်းမှာတင် Key တွေကို ပိုပြီး ပြည့်ကျပ်နေအောင် ဆွဲထည့်နိုင်ပါတယ်။ Page တစ်ခုမှာ Key များများဆန့်လေလေ၊ Tree ရဲ့ Level Depth က ပိုတိုလေလေပါပဲ။ Tree ပိုတိုတော့ ဒေတာရှာဖို့ Page Read အနည်းငယ်ပဲ လိုတော့တယ်။ Page Read တိုင်းဟာ I/O Operation တစ်ခုဖြစ်ပြီး ဒါဟာ SQLite ရဲ့ ကုန်ကျစရိတ် အကြီးဆုံး အပိုင်းပါပဲ။
2. Range Query များ ပိုမြန်လာခြင်း: ဒေတာအားလုံးဟာ Leaf Node တွေမှာပဲ ရှိနေပြီး အဲဒီ Leaf Node တွေကို Chain လိုမျိုး တစ်ခုနဲ့တစ်ခု ချိတ်ဆက်ထားပါတယ်။ ဒါကြောင့် BETWEEN လို Range Query တွေမှာ Range ရဲ့ အစကို Tree ထဲမှာ တစ်ခါပဲ ရှာလိုက်ရုံပါပဲ။ အဲဒီနောက်မှာတော့ Leaf Page Chain အတိုင်း ရှေ့ဆက်ဖတ်သွားရုံနဲ့ ဒေတာတွေ အကုန်ရပါတယ်။ Row တိုင်းအတွက် Tree ကို အပေါ်အောက် ပြန်တက်ပြန်ဆင်း လုပ်နေစရာ မလိုတော့ပါဘူး။

SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-03-31';

SQLite ဟာ ပထမဆုံး ကိုက်ညီတဲ့ Row ကို Tree ထဲမှာ အရင်ရှာတယ်၊ ပြီးတာနဲ့ Range ကျော်မသွားမချင်း Leaf Page တွေနောက်ကို တောက်လျှောက် လိုက်ဖတ်သွားပါတယ်။ ရိုးရှင်းတယ်၊ ဒါပေမဲ့ အရမ်းမြန်ပါတယ်။

Page အမျိုးအစား သုံးမျိုး

SQLite ရဲ့ B+tree implementation မှာ Page သုံးမျိုးကို သုံးပါတယ်။ Part-1 မှာ ပြောခဲ့သလိုပဲ .db file တစ်ခုလုံးဟာ Fixed-size ရှိတဲ့ Page တွေ (Default 4096 bytes) နဲ့ ဖွဲ့စည်းထားတာပါ။ B-tree ကတော့ ဒီ Page တွေကို သီးခြား Role တွေ ပေးလိုက်တာပဲ ဖြစ်ပါတယ်။

Interior Pages (လမ်းညွှန်လွှာ) Interior page တွေဟာ Navigation layer တွေပါ။ Actual row data တွေ သူတို့မှာ မရှိပါဘူး။ မှန်ကန်တဲ့ Leaf page ဆီကို SQLite ရောက်သွားအောင် လမ်းညွှန်ပေးမယ့် Key တွေနဲ့ Pointer တွေပဲ ရှိပါတယ်။

Interior page တစ်ခုမှာ ပါဝင်တာတွေကတော့:

• Key list: Row ID တွေ ဒါမှမဟုတ် Indexed column value တွေပါ။
• Child page pointers: Key တစ်ခုချင်းစီအတွက် Pointer တစ်ခုစီနဲ့ ညာဘက်အစွန် (Right side) အတွက် Pointer တစ်ခု ပါပါတယ်။

Interior page တွေဟာ Compact ဖြစ်တဲ့အတွက် 4KB page တစ်ခုမှာတင် Key ပေါင်း ရာနဲ့ချီ ဆန့်ပါတယ်။ ဒါကြောင့် SQLite ရဲ့ Tree တွေဟာ အလွန် “ကျယ်ပြန့်ပြီး တိုတောင်း” ပါတယ်။ Row သန်းနဲ့ချီတဲ့ Table တွေမှာတောင် Tree Level ဟာ ၂ ကနေ ၄ အထိပဲ ရှိတတ်တာဟာ ဒီကြောင့်ပါ။

Leaf Pages (ဒေတာလွှာ) Leaf page တွေဟာ Actual data တွေ တကယ်ရှိနေတဲ့ နေရာပါ။ Page တစ်ခုချင်းစီမှာ Cell တွေ အစဉ်လိုက် ရှိနေပြီး Cell တစ်ခုဟာ Row တစ်ကြောင်း (Record တစ်ခု) ကို ကိုယ်စားပြုပါတယ်။

Cell တစ်ခုမှာ ပါဝင်တာတွေကတော့:

• Row Key: Rowid ဒါမှမဟုတ် Primary key value။
• Actual Payload: Column value တွေအကုန်လုံးကို SQLite ရဲ့ Record format နဲ့ Serialize လုပ်ပြီး သိမ်းထားတာပါ။

Leaf page ပေါ်က Cell တွေကို Key အလိုက် Sorလုပ်ထားတဲ့အပြင် အနီးအနားက Page တွေနဲ့လည်း Chain လို ချိတ်ဆက်ထားပါတယ်။ ဒါကြောင့် Range Scan လုပ်တဲ့အခါ Tree တစ်ခုလုံးကို ပြန်မပတ်ဘဲ Page Chain အတိုင်း တောက်လျှောက် ဖတ်သွားရုံပါပဲ။

Overflow Pages (ပိုလျှံလွှာ) ဒီနေရာမှာတော့ SQLite ရဲ့ Page-based model က Constraint တစ်ခုနဲ့ တိုးပါတယ်။ Row တစ်ခုရဲ့ Data ဟာ Cell တစ်ခုထဲ ဝင်ရမယ်၊ Cell ဟာ Page တစ်ခုထဲမှာ ဝင်ရမယ်။ ဒါပေမဲ့ 50KB JSON Blob လိုမျိုး Page တစ်ခု (4KB) ထက် ကြီးနေရင် ဘာဖြစ်မလဲ?

SQLite ဟာ ဒါကို Overflow pages တွေနဲ့ ကိုင်တွယ်ပါတယ်။ Record ရဲ့ Payload က သတ်မှတ်ထားတဲ့ Limit ထက် ကျော်သွားရင် ပိုလျှံတဲ့ Data တွေကို Overflow page တစ်ခု (သို့မဟုတ်) အများကြီးထဲကို ခွဲထုတ်လိုက်ပါတယ်။ Leaf page ပေါ်က Cell မှာတော့ Payload ရဲ့ အစပိုင်းလေးနဲ့အတူ ပထမဆုံး Overflow page ကို ညွှန်တဲ့ Pointer လေးပဲ ကျန်ခဲ့ပါတော့တယ်။

ဒါဟာ User အနေနဲ့ မသိသာပေမဲ့ Performance Implication တော့ ရှိပါတယ်။ Large Blob တွေကို ဖတ်တဲ့အခါ Page တစ်ခုတည်း မဟုတ်ဘဲ Page အများကြီးကို လိုက်ဖတ်ရတာကြောင့် I/O ကုန်ကျစရိတ် ပိုများသွားမှာကို သတိထားဖို့ လိုပါတယ်။

Table တစ်ခုမှာ Tree နှစ်မျိုး

ဒါဟာ SQLite ကို စတင်လေ့လာသူတွေ မျှော်လင့်မထားဘဲ ထိမိတတ်တဲ့ အချက်တစ်ခုပါပဲ။ Index ရှိတဲ့ Table တစ်ခုအတွက် SQLite ဟာ B+tree နှစ်မျိုးကို သီးခြားစီ ထိန်းသိမ်းထားတာ ဖြစ်ပါတယ်။ Table ကိုယ်တိုင်အတွက် တစ်ပင်နဲ့ Index တစ်ခုချင်းစီအတွက် တစ်ပင်စီပေါ့။

Table B-Tree (Rowid Table) ပုံမှန် SQLite table တစ်ခုအတွက် Primary B+tree ဟာ Rowid ကို Key အဖြစ် သုံးပါတယ်။ ဒါဟာ Row တစ်ကြောင်းချင်းစီကို Uniquely Identify လုပ်ပေးတဲ့ 64-bit Integer တစ်ခုပါ။ Table မှာ INTEGER PRIMARY KEY Column ရှိနေတယ်ဆိုရင် အဲဒီ Column ကိုယ်တိုင်က Rowid ဖြစ်သွားပါတယ်။ Table ရဲ့ B-tree ဟာ ဒီ Rowid ကိုပဲ အခြေခံပြီး ဒေတာတွေကို စနစ်တကျ Organize လုပ်ထားတာပါ။

ဒါကြောင့် Rowid ကို သုံးပြီး Row တစ်ကြောင်းကို Lookup လုပ်တာဟာ B-tree Traversal ကိုတစ်ကြိမ်တည်းနဲ့တင် ပြီးသွားစေပါတယ်။ ဒါဟာ အရမ်းမြန်ပြီး တိုက်ရိုက်ဖြစ်သလို ကြာမယ့်အချိန်ကိုလည်း အတိအကျ ခန့်မှန်းနိုင်ပါတယ်။

Index B-Tree Index တစ်ခု Create လုပ်လိုက်တဲ့ အချိန်မှာတော့-

CREATE INDEX idx_users_email ON users(email);

SQLite ဟာ Table B-tree နဲ့ သီးခြားဖြစ်တဲ့ ဒုတိယ B-tree တစ်ပင်ကို ထပ်မံတည်ဆောက်လိုက်ပါတယ်။ ဒီ Index Tree ဟာ Indexed Column Value (ဒီနေရာမှာဆိုရင် email address) ကို Key အဖြစ် သုံးပါတယ်။ ဒါပေမဲ့ သူ့ရဲ့ Leaf Node တွေထဲမှာ Row Data အပြည့်အစုံ မပါပါဘူး။ ပါဝင်တာကတော့ Indexed Column Value + Matching Row ရဲ့ Rowid ပဲ ဖြစ်ပါတယ်။

ဒါကြောင့် ဒီ Index ကို သုံးတဲ့ Query တစ်ကြောင်းဟာ Lookup နှစ်ကြိမ် လုပ်ရပါတယ်။

1. Email ကိုရှာဖို့ Index B-tree ထဲမှာ လိုက်ရှာပြီး အဲဒီ Row ရဲ့ Rowid ကို အရင်ယူရတယ်။
2. ရလာတဲ့ Rowid ကို သုံးပြီး Table B-tree ထဲမှာ တကယ့် Full Row Data ကို ရဖို့ တစ်ခါထပ်ရှာရတယ်။

ဒီလုပ်ငန်းစဉ်ကို Double-lookup (သို့မဟုတ်) Bookmark Lookup လို့ ခေါ်ကြပါတယ်။ တစ်ခါတလေမှာ Row အများအပြားနဲ့ ကိုက်ညီနေတဲ့ Query မျိုးဆိုရင် SQLite ရဲ့ Query Planner က ဒီ Two-step process (Index သုံးတာ) ထက် Full Table Scan (တစ်ကြောင်းချင်းဖတ်တာ) က ပိုသက်သာတယ်လို့ ဆုံးဖြတ်တတ်ပါတယ်။ ဒါကိုတော့ Part-8 မှာ EXPLAIN QUERY PLAN နဲ့ အသေးစိတ် ကြည့်ကြပါမယ်။

WITHOUT ROWID: အခြားနည်းလမ်းတစ်ခု

SQLite မှာ အထက်ကပြောခဲ့တဲ့ Double-lookup Model ကို လုံးဝပြောင်းလဲပစ်နိုင်တဲ့ Table Type တစ်ခုရှိပါတယ်။ အဲဒါကတော့ WITHOUT ROWID Table တွေပါပဲ။

CREATE TABLE sessions (
    token TEXT PRIMARY KEY,
    user_id INTEGER,
    expires_at INTEGER
) WITHOUT ROWID;

ဒီ Table အမျိုးအစားမှာတော့ SQLite ဟာ Primary Key ကိုယ်တိုင်ကို B-tree Key အဖြစ် တိုက်ရိုက်အသုံးပြုပါတယ်။ ထူးခြားချက်ကတော့ Index Tree ထဲမှာတင် Full Row Data ကို တစ်ခါတည်း သိမ်းဆည်းလိုက်တာပါ။ သီးခြား Table B-tree ဆိုတာ မရှိတော့ဘဲ Index ကိုယ်တိုင်က Table ဖြစ်သွားတဲ့သဘော ပါပဲ။ တခြား Database စနစ်တွေမှာတော့ ဒါကို Clustered Index လို့ ခေါ်ကြပါတယ်။

• ရရှိတဲ့ အကျိုးကျေးဇူး(Benefit): အကယ်၍ Primary Key နဲ့ Row တွေကို အမြဲ Lookup လုပ်နေရသူဆိုရင် Double-lookup လုပ်ရတဲ့ဒုက္ခကို လုံးဝ ကျော်ဖြတ်နိုင်သွားပါပြီ။ B-tree Traversal လမ်းကြောင်းတစ်ခုတည်းနဲ့တင် Row Data တစ်ခုလုံးကို ရရှိမှာ ဖြစ်ပါတယ်။
• လဲလှယ်ရတဲ့အချက် (Trade-offs): ဒါပေမဲ့ WITHOUT ROWID Table တွေဟာ Flexibility နည်းပါတယ်။ သူတို့မှာ Explicit Primary Key အတိအလင်း ပါရမယ်၊ Auto-increment Row ID ကို Support မလုပ်ဘူး၊ ပြီးတော့ Primary Key မဟုတ်တဲ့ တခြား Column တွေနဲ့ Scan ဖတ်ရတဲ့ Query တွေမှာ ပိုပြီး နှောင့်နှေးသွားနိုင်ပါတယ်။

ဒါပေမဲ့ တည်ငြိမ်တဲ့ Natural Primary Key (ဥပမာ- Token သို့မဟုတ် UUID) တွေပေါ်မှာ Point Lookup နဲ့ Range Scan လုပ်ရတဲ့ Access Pattern မျိုးအတွက်ဆိုရင်တော့ WITHOUT ROWID ဟာ သိသိသာသာကို ပိုမြန်ဆန်စေမှာပါ။

Tree ဘာကြောင့် Balanced ဆက်ရှိနေတာလဲ?

Unbalanced ဖြစ်သွားတဲ့ B-tree ဆိုတာ နှေးကွေးသွားတဲ့ B-tree ပါပဲ။ ဥပမာ-Tree ရဲ့ Branch တစ်ခုက Level ၃ ဆင့်ပဲရှိပြီး နောက်တစ်ခုက Level ၁၂ ဆင့်လောက် ဖြစ်နေမယ်ဆိုရင် ဒေတာရှာရမယ့်အချိန် (Lookup Time) ကို ဘယ်လိုမှ ခန့်မှန်းလို့ မရနိုင်တော့ပါဘူး။ Leaf Node အားလုံးဟာ အနက် Depth တူညီရမယ်ဆိုတဲ့ Guarantee ဟာ Performance ကို အမြဲတမ်း Consistent ဖြစ်နေစေတဲ့ အဓိကသော့ချက်ပါပဲ။

SQLite ဟာ Splitting နဲ့ Merging ဆိုတဲ့ Operation နှစ်ခုကို သုံးပြီး ဒီ Balance ကို အလိုအလျောက် ထိန်းသိမ်းပေးပါတယ်။

• Splitting: Page တစ်ခု ပြည့်သွားပြီး Entry အသစ်တစ်ခု ထပ်ထည့်ဖို့ လိုလာတဲ့အခါ SQLite ဟာ အဲဒီ Page ကို နှစ်ခု ခွဲလိုက်ပါတယ်။ အလယ်က Median Key ကတော့ Separator အသစ်တစ်ခုအနေနဲ့ အပေါ်က Parent Page ဆီကို တက်သွားပါတယ်။ တကယ်လို့ Parent Page ပါ ပြည့်နေမယ်ဆိုရင် သူလည်း ထပ်ခွဲပါတယ်။ ဒါဟာ Root အထိ ကူးစက် (Cascade) သွားနိုင်ပါတယ်။ Root ကို ခွဲလိုက်ရတဲ့အခါမှာတော့ Root အသစ်တစ်ခု ထပ်တိုးလာပြီး Tree ရဲ့ Level ဟာ တစ်ဆင့် မြင့်တက်သွားပါတယ်။
• Merging: Row တွေကို Delete လုပ်လိုက်လို့ Page တွေက အရမ်း ဟာလာဟင်းလင်း ဖြစ်သွားတဲ့အခါ (Under-full) SQLite ဟာ အိမ်နီးချင်း Page တွေကို ပြန်ပေါင်းပေးနိုင်ပါတယ်။ အပေါ်က Parent ဆီက Key တွေ ပြန်ဆင်းလာတယ်၊ Parent က ကျုံ့သွားတယ်၊ တကယ်လို့ Parent ပါ ဗလာဖြစ်သွားရင် Tree ရဲ့ Level ဟာ တစ်ဆင့် ပြန်လျော့သွားပါတယ်။

ဒါတွေအားလုံးဟာ ကိုယ်တိုင် မြင်တွေ့နေရမှာ မဟုတ်ဘဲ နောက်ကွယ်မှာ အလိုအလျောက် ဖြစ်ပျက်နေတာပါ။ Row တစ်ကြောင်း Insert လုပ်တိုင်း SQLite က Rebalancing ကို ကိုင်တွယ်သလို၊ Row တစ်သန်း Delete လုပ်ရင်လည်း Consolidation ကို လုပ်ဆောင်ပါတယ်။ ဒါကြောင့် Tree ဟာ အမြဲတမ်း Balanced ဖြစ်နေတယ်၊ Depth ကလည်း Uniform ဖြစ်နေတယ်၊ Lookup Time ကလည်း Logarithmic အတိုင်း တည်ငြိမ်မြန်ဆန်နေတာ ဖြစ်ပါတယ်။

အကုန်ပေါင်းစပ်ထားတဲ့ Full Lookup တစ်ခု

ဒီ Query ကို Run လိုက်တဲ့အချိန်မှာ-

SELECT email FROM users WHERE id = 42;

B-tree ရဲ့ အမြင်ကနေ တကယ်ဖြစ်ပျက်သွားတာကတော့ အောက်ပါအတိုင်းပါပဲ:

1. အစပြုခြင်း: SQLite ဟာ users table ရဲ့ B-tree က ဘယ် Page မှာ စတင်သလဲဆိုတာ သိဖို့ Database Header (Page 1) ကို အရင်ဖတ်ပါတယ်။
2. Root သို့ သွားခြင်း: အဲဒီ B-tree ရဲ့ Root Page ကို ဖတ်ပါတယ်။ ဒါဟာ ပုံမှန်အားဖြင့် Interior Page တစ်ခုပါ။
3. လမ်းကြောင်းရှာခြင်း: id = 42 ဆီကို ဦးတည်မယ့် Child Pointer ကို ရှာဖို့ Root Page ထဲက Key တွေကို Binary Search နဲ့ အမြန်စစ်ပါတယ်။
4. အဆင့်ဆင့် ဆင်းသွားခြင်း: အဲဒီ Child Page ကို ဆက်ဖတ်ပါတယ်။ ဒါဟာ နောက်ထပ် Interior Page တစ်ခုလည်း ဖြစ်နိုင်သလို၊ Leaf Page လည်း ဖြစ်နိုင်ပါတယ်။
5. ပန်းတိုင်သို့ ရောက်ခြင်း: Actual Data ရှိတဲ့ Leaf Page တစ်ခုကို ရောက်တဲ့အထိ ဒီအတိုင်း ဆက်သွားပါတယ်။
6. Data ဆွဲထုတ်ခြင်း: Leaf Page ထဲ ရောက်ပြီဆိုရင် id = 42 ပါတဲ့ Cell ကို ရှာဖို့ Binary Search တစ်ခါ ထပ်လုပ်ပါတယ်။
7. ရလဒ်ပေးခြင်း: အဲဒီ Record ထဲကနေမှ email column ကို Return ပြန်ပေးလိုက်တာပါ။

Row သန်းနဲ့ချီတဲ့ Table တစ်ခုအတွက်ဆိုရင်တောင် ဒါဟာ Page စုစုပေါင်း ၄ ကနေ ၅ ကြောင်းလောက်ပဲ ဖတ်ရမယ်လို့ ဆိုလိုတာပါ။ Page တစ်ကြောင်းဟာ 4KB ဆိုတော့ Row ၁၀ သန်းရှိတဲ့ Table ကြီးမှာတောင် Lookup တစ်ကြိမ်ဟာ I/O 20KB ဝန်းကျင်ပဲ ကုန်ကျပါတယ်။ တကယ်လို့ ခဏခဏသုံးနေတဲ့ (Hot) Page တွေက Memory (Page Cache) ထဲမှာ ရှိနေမယ်ဆိုရင်တော့ Disk I/O လုံးဝမရှိဘဲ Instant ဖြစ်သွားမှာပါ။

ဒါဟာ B-tree ကို ဒီဇိုင်းဆွဲထားတဲ့အတိုင်း တိတိကျကျနဲ့ အကျိုးရှိရှိ အလုပ်လုပ်နေတာပဲ ဖြစ်ပါတယ်။

မှတ်မိဖို့ကောင်းတဲ့ Mental Model

SQLite ရဲ့ B-tree ကို ကောင်းကောင်းစီမံထားတဲ့ Library ကြီးတစ်ခုလို စဉ်းစားကြည့်ရင် ပိုမြင်သာပါတယ်။

• Root Page ဟာ Main Catalog ပါ။ စာအုပ်တွေ သူ့မှာမရှိပေမဲ့ ဘယ် Section ကို သွားရမလဲဆိုတာ ပြောပြပေးပါတယ်။
• Interior Pages တွေဟာ Section ဆိုင်းဘုတ်တွေပါ။ ဒီနေရာကနေ မှန်ကန်တဲ့ Shelf ဆီကိုပဲ ညွှန်ပြပေးပါတယ်။
• Leaf Pages ကတော့ Shelf ကိုယ်တိုင်ပါပဲ။Actual Data တွေ အစီအစဉ်တကျ ရှိနေတဲ့နေရာပါ။ Shelf ပေါ်ရောက်သွားရင်တော့ ဘယ်ညာရွှေ့ကြည့်ပြီး ကိုယ်လိုချင်တဲ့စာအုပ်ကို ရှာဖို့ အရမ်းလွယ်ကူသွားပါပြီ။

စာအုပ်တစ်အုပ်ကို ရှာတဲ့အခါ Catalog → Section → Shelf → Book ဆိုတဲ့ အစီအစဉ်အတိုင်း သွားပါတယ်။ စာကြည့်တိုက်ထဲက စာအုပ်တိုင်းကို လိုက်စစ်နေစရာ မလိုပါဘူး။ Shelf တိုင်းဟာ Entrance ကနေ အကွာအဝေး တူညီတဲ့အတွက် (Balanced) ရှာရမယ့်အချိန်ကို အမြဲတမ်း ကြိုတင်ခန့်မှန်းနိုင်ပါတယ်။

ဒီလို ခန့်မှန်းနိုင်မှု (Logarithmic access)၊ အမြဲတမ်း ညီမျှနေမှု (Guaranteed balance) နဲ့ အစဉ်လိုက်ဖြစ်နေမှု (Sorted leaf chain) တွေကြောင့်ပဲ B-tree ဟာ နှစ်ပေါင်း ၅၀ ကျော်တိုင်အောင် Storage စနစ်ကြီးတွေရဲ့ Core Data Structure) ဖြစ်နေရတာပါ။ SQLite ဟာ ဒီအမွေကို ဆက်ခံပြီး ပိုမိုသပ်ရပ်အောင် ဆောင်ရွက်ကာ အခြားအရာတွေ အားလုံးကို ၎င်းပေါ်မှာ ခိုင်ခိုင်မာမာ တည်ဆောက်ထားပါတယ်။

For The Part-7 (Indexing Deep Dive)

Part-7 မှာတော့ Index တွေကို ပိုပြီး နက်နက်နဲနဲ ကြည့်ကြပါမယ်။

Freelist နဲ့ B-tree အကြောင်း သိပြီးတဲ့နောက်မှာတော့ Storage Level မှာ Index တွေကြောင့် တကယ် ဘာတွေ ဖြစ်ကုန်သလဲဆိုတာ ပိုမြင်သာလာပါလိမ့်မယ်။ Query Planner ဟာ Index တွေကို ဘယ်လိုအချိန်မှာ သုံးဖို့ ဆုံးဖြတ်သလဲ၊ ပြီးတော့ Index တစ်ခုဟာ Query တွေကို ပိုမြန်စေမယ့်အစား ဘယ်လိုအခြေအနေမျိုးမှာ ပိုဆိုးသွားစေသလဲ (Overhead) ဆိုတာတွေကိုလည်း အသေးစိတ် ဆွေးနွေးသွားပါမယ်။

ဒါ့အပြင် Index တွေက Disk Space ကို ဘယ်လိုသုံးသလဲနဲ့ Write Performance အပေါ် ဘယ်လို သက်ရောက်မှုရှိသလဲဆိုတာကိုပါ ခြုံငုံသုံးသပ်သွားမှာ ဖြစ်ပါတယ်။