B+tree — จาก 3,153 หน้าเหลือ 3 หน้าที่แตะ
บท 2 ปิดด้วยข้อจำกัดข้อเดียวของ heap file คือมันไม่มีทางรู้ล่วงหน้าว่าหน้าไหนไม่ต้องอ่าน ทุกคำถามจึงจ่ายเท่ากันหมดคือ 3,153 หน้า
บทนี้ประกอบโครงสร้างที่บอกได้ก่อนอ่านว่าหน้าไหนต้องอ่าน แล้ววัดว่ามันลดจำนวนหน้าที่แตะลงเหลือเท่าไร
คำตอบคือ 3 หน้า แต่ตัวเลขที่ให้อะไรมากกว่านั้นคือเหตุผลว่าทำไมถึงเป็น 3 และทำไมมันแทบไม่โตตามขนาดข้อมูล
บทนี้เพิ่ม file เดียวคือ qe/bptree.py วางไว้ข้าง qe/fixture.py ของบท 1 กับ qe/heapfile.py ของบท 2 มันเรียกใช้ทั้งสอง file นั้นตรงๆ จึงต้องมีครบก่อนถึงจะรันได้
รันจาก folder ทำงานด้านนอกเหมือนสองบทก่อน ด้วย python3 qe/bptree.py ตัวเลขผลวัดในบทนี้คือ stdout ของคำสั่งเดียวนั้น ส่วนตัวเลขที่มาจากสูตรจะติดป้ายกำกับไว้ทุกจุด
จุดที่ heap ตัน และเงื่อนไขของสิ่งที่จะมาแทน
หัวข้อที่มีชื่อว่า “จุดที่ heap ตัน และเงื่อนไขของสิ่งที่จะมาแทน”สิ่งที่ heap file ทำไม่ได้ และเงื่อนไขสามข้อที่โครงสร้างใหม่ต้องผ่านก่อนจะเอามาใช้ได้
heap file เก็บแถวตามลำดับที่เขียนเข้าไป และไม่มีที่ไหนบันทึกไว้เลยว่าค่าไหนอยู่หน้าไหน การถามว่า “ออเดอร์ที่สั่งวันนี้มีกี่รายการ” จึงตอบได้ทางเดียวคืออ่านทุกหน้าแล้วกรองทิ้งเอง
ทางแก้ที่คนคิดถึงก่อนคือทำ dict ในหน่วยความจำ ราคาของมันคือต้องยกข้อมูลทั้งชุดขึ้นแรม สร้างใหม่ทุกครั้งที่ process เริ่ม และตอบคำถามแบบช่วงไม่ได้
โครงสร้างที่บทนี้จะสร้างจึงต้องผ่านสามข้อ
- อยู่บนหน้า 4096 byte แบบเดียวกับ heap เพื่อให้หน่วยที่คอร์สนี้นับ คือจำนวนหน้าที่แตะ ใช้กับทั้งสองฝั่งได้ตรงๆ
- ตอบได้ทั้งค่าเดียวและช่วง เพราะคำถามจริงส่วนใหญ่เป็นช่วง ไม่ใช่การถามค่าเป๊ะๆ ค่าเดียว
- ชี้กลับไปที่แถวจริงด้วย record id ไม่เก็บตัวแถวซ้ำอีกชุด
B+treeB+treeต้นไม้ค้นหาที่ทุกโหนดเป็นหนึ่งหน้า เก็บคีย์กับตัวชี้ของข้อมูลจริงไว้ที่ใบทั้งหมด และร้อยใบต่อกันเป็นโซ่ จึงตอบได้ทั้งการค้นค่าเดียวและการค้นเป็นช่วง ผ่านทั้งสามข้อ ราคาที่จ่ายมีสองข้อ คือกินที่บน disk เพิ่ม ซึ่งบทนี้วัดให้ดู กับต้องเขียนตามทุกครั้งที่ตารางเปลี่ยน ซึ่งบทนี้ไม่ได้จ่ายและไม่ได้วัด
เพราะ B+tree ของคอร์สนี้ตัดเรื่อง delete ออกทั้งหมด ต่อจากเส้นขอบเขตของ heap ที่บท 1 ประกาศไว้ว่าเขียนต่อท้ายอย่างเดียว มันสร้างครั้งเดียวจากข้อมูลที่มีอยู่แล้ว แล้วอ่านอย่างเดียว
fanout ไม่ใช่ค่าที่เลือกเอง มันตกลงมาจากเลขคณิตของหน้าเดียว
หัวข้อที่มีชื่อว่า “fanout ไม่ใช่ค่าที่เลือกเอง มันตกลงมาจากเลขคณิตของหน้าเดียว”การเดินเลขคณิตจากขนาดหน้า 4096 byte ลงไปถึงจำนวนกิ่งที่ node หนึ่ง node แตกได้
ค่าคงที่ทั้งชุดของ B+tree นี้ไม่มีตัวไหนถูกพิมพ์ทับด้วยเลขที่คิดมาก่อน ทุกตัวคำนวณจากขนาดหน้า
import osimport struct
from heapfile import PAGE_SIZE, Pager, build_heap, decode, read_slotimport fixture
# ── รูปแบบไบต์ของโหนด (ทุก format ขึ้นต้นด้วย '<' ให้ชัดว่า little-endian) ──NODE_HDR = struct.Struct("<BHI") # (is_leaf, nkeys, next_leaf) = 7 BKEY = struct.Struct("<I") # placed_at (unix time) = 4 BCHILD = struct.Struct("<I") # เลขหน้าของลูก = 4 BRID = struct.Struct("<IH") # (pageno, slot) ของ heap = 6 BMETA = struct.Struct("<III") # (root, height, nentries) อยู่หน้าที่ 0
HDR_SIZE = NODE_HDR.size # 7BODY = PAGE_SIZE - HDR_SIZE # 4089 — ที่ว่างจริงในหนึ่งหน้า
LEAF_ENTRY = KEY.size + RID.size # 10 B ต่อหนึ่งรายการในใบLEAF_MAX = BODY // LEAF_ENTRY # รายการสูงสุดต่อใบ
# โหนดใน: n คีย์ ต้องมีตัวชี้ n+1 ตัว → KEY*n + CHILD*(n+1) <= BODYINNER_MAX_KEYS = (BODY - CHILD.size) // (KEY.size + CHILD.size)FANOUT = INNER_MAX_KEYS + 1 # จำนวนทางที่แตกได้ต่อโหนดใน
KEYS_OFF = HDR_SIZE # คีย์ของโหนดในเริ่มตรงนี้CHILDREN_OFF = KEYS_OFF + INNER_MAX_KEYS * KEY.size # ตามด้วยตัวชี้ลูกNO_NEXT = 0xFFFFFFFF # ใบขวาสุดไม่มีใบถัดไปหัวของทุก node ใช้ format <BHI> เก็บสามค่าคือธงว่าเป็นใบหรือไม่ จำนวนคีย์ในหน้านั้น และเลขหน้าของใบถัดไป รวมเป็น 7 byte เท่ากันทั้งใบและ node ที่ไม่ใช่ใบ
| ช่องในหนึ่งหน้า | ขนาด |
|---|---|
| หนึ่งหน้า | 4096 B |
หัว node <BHI> | 7 B |
| เหลือให้ข้อมูล | 4089 B |
ที่เหลือ 4089 byte คือทั้งหมดที่เอาไปใส่ของได้ และของที่ใส่มีสองแบบตามชนิดของ node
ใบเก็บคู่ของคีย์กับ record id คีย์คือ placed_at เก็บด้วย <I> กิน 4 byte ส่วน record id คือคู่ของเลขหน้ากับหมายเลข slot เก็บด้วย <IH> กิน 6 byte รวมหนึ่งรายการ 10 byte พอดี
4089 หารด้วย 10 ปัดลงได้ 408 นี่คือจำนวนรายการสูงสุดที่ใบหนึ่งใบรับได้
node ที่ไม่ใช่ใบเก็บคีย์กับตัวชี้ลูก และมันไม่สมมาตร เพราะคีย์ n ตัวแบ่งช่วงออกเป็น n+1 ช่วง จึงต้องมีตัวชี้ n+1 ตัวเสมอ เงื่อนไขจึงเป็น 4n + 4(n+1) ≤ 4089
แก้สมการได้ n สูงสุดเท่ากับ (4089 − 4) หารด้วย (4 + 4) ปัดลงเหลือ 510 คีย์ และตัวชี้ 511 ตัว
ตัวเลข 511 นั้นคือ fanoutfanoutจำนวนกิ่งที่โหนดในหนึ่งโหนดชี้ออกไปได้ ไม่ใช่ค่าที่เลือกเอง แต่ตกลงมาจากเลขคณิตของหน้าเดียว (เนื้อที่ในหน้าหารด้วยขนาดของหนึ่งรายการ) ยิ่งสูงต้นไม้ยิ่งเตี้ย ของโครงสร้างนี้ ไม่มีใครเลือกมัน มันเป็นผลหารของขนาดหน้ากับขนาดของหนึ่งรายการ เปลี่ยนขนาดหน้าหรือขนาดคีย์เมื่อไร ตัวเลขนี้ก็เปลี่ยนตามทันที
คีย์ 510 ตัวใน node ที่ไม่ใช่ใบไม่ใช่ข้อมูล มันคือ separator keyseparator keyคีย์ในโหนดในที่ทำหน้าที่บอกทางลงเท่านั้น ไม่ใช่ข้อมูลจริง มันแบ่งว่าคีย์ที่กำลังค้นควรลงไปทางกิ่งไหน ที่มีหน้าที่เดียวคือบอกว่าคีย์ที่กำลังค้นควรลงไปทางกิ่งไหน ค่าจริงกับ record id อยู่ที่ใบทั้งหมด
ทั้งใบและ node ที่ไม่ใช่ใบใช้การค้นแบบ binary search ในหน้าเดียวกันหมด และมันมี parameter ตัวหนึ่งที่ตัดสินเรื่องคีย์ซ้ำ
def leaf_search(page, n, key, right): """ค้นแบบทวิภาคในใบ อ่านไบต์ตรง ๆ ไม่สร้าง list (นี่คือทางร้อนตอน insert)
right=False → ตำแหน่งซ้ายสุดที่คีย์ >= key (ใช้ตอนค้นหา) right=True → ตำแหน่งขวาสุดที่คีย์ <= key (ใช้ตอนแทรก) """ lo, hi = 0, n while lo < hi: mid = (lo + hi) // 2 k = KEY.unpack_from(page, HDR_SIZE + mid * LEAF_ENTRY)[0] if (k <= key) if right else (k < key): lo = mid + 1 else: hi = mid return loplaced_at มีค่าซ้ำอยู่จริงในข้อมูลชุดนี้ ถ้าค้นด้วย right=True การค้นจะข้ามไปหลังตัวซ้ำตัวสุดท้าย ซึ่งถูกตอนแทรกเพราะทำให้ของใหม่ไปต่อท้ายพวกเดียวกัน แต่ผิดตอนค้นเพราะจะข้ามคำตอบตัวแรกไป
การค้นจึงใช้ right=False เสมอ ส่วนการแทรกใช้ right=True เสมอ นี่คือทั้งหมดของวิธีจัดการคีย์ซ้ำในโครงสร้างนี้
นโยบายแตกหน้าเปลี่ยนความสูงของต้นไม้ได้ ทั้งที่ข้อมูลชุดเดียวกันเป๊ะ
หัวข้อที่มีชื่อว่า “นโยบายแตกหน้าเปลี่ยนความสูงของต้นไม้ได้ ทั้งที่ข้อมูลชุดเดียวกันเป๊ะ”ผลวัดของการใส่คีย์ครบสองแสนตัวด้วยสองนโยบาย และผลที่ตามมาต่อความสูงกับขนาดของต้นไม้
ตอนใบเต็มแล้วมีของใหม่เข้ามา ต้องแบ่งใบนั้นเป็นสองใบ จุดที่ตัดเป็นเรื่องของนโยบาย และ code เก็บไว้ทั้งสองแบบเพื่อให้เทียบกันได้
def _split_leaf(self, pno, page, n, nxt, pos, key, rid): entries = leaf_entries(page) entries.insert(pos, (key, rid[0], rid[1])) if self.append_split and nxt == NO_NEXT and pos == n: cut = n # ต่อท้ายใบขวาสุด → ปล่อยให้ใบซ้ายเต็ม else: cut = (n + 1) // 2 # กรณีทั่วไป — หั่นครึ่ง rpage = new_node(True) rpno = self._alloc(rpage) leaf_pack(page, entries[:cut]) leaf_pack(rpage, entries[cut:]) set_header(page, 1, cut, rpno) # ร้อยโซ่ใบ: ซ้าย -> ใหม่ -> เดิม set_header(rpage, 1, len(entries) - cut, nxt) return entries[cut][0], rpnoเงื่อนไขสามข้อบนบรรทัด if คือหัวใจ มันตัดท้ายก็ต่อเมื่อใบนั้นเป็นใบขวาสุดจริง และของใหม่ตกลงมาที่ตำแหน่งท้ายสุดจริง กรณีอื่นทั้งหมดตกไปที่การหั่นครึ่ง
ผลของสองนโยบายบนข้อมูลชุดเดียวกันเป๊ะ ต่างกันแบบนี้
| แตกแบบตัดท้าย | แตกแบบหั่นครึ่ง | |
|---|---|---|
| ความสูง | 2 ชั้น | 3 ชั้น |
| ราก | 1 node · 490 คีย์ | 1 node · 2 คีย์ |
| ชั้นกลาง | ไม่มี | 3 node · 977 คีย์ |
| ใบ | 491 node | 980 node |
| ทั้งต้น | 492 หน้า (15.6 % ของ heap) | 984 หน้า (31.2 % ของ heap) |
| ใบเต็มเฉลี่ย | 99.8 % | 50.0 % |
flowchart LR
D["คีย์ชุดเดียวกัน 200,000 ตัว"]
D --> A["แตกแบบตัดท้าย<br/>ใบเต็มเฉลี่ย 99.8 %"]
D --> B["แตกแบบหั่นครึ่ง<br/>ใบเต็มเฉลี่ย 50.0 %"]
A --> A2["ใบ 491 node"]
B --> B2["ใบ 980 node"]
A2 --> A3["สูง 2 ชั้น<br/>ทั้งต้น 492 หน้า"]
B2 --> B3["สูง 3 ชั้น<br/>ทั้งต้น 984 หน้า"]
คำบรรยายภาพ: ข้อมูลชุดเดียวกันเป๊ะเดินผ่านนโยบายแตกหน้าคนละแบบ แล้วได้ต้นไม้คนละความสูง · เส้นบนคือการตัดท้ายซึ่งปล่อยให้ใบซ้ายเต็มก่อนเปิดใบใหม่ · เส้นล่างคือการหั่นครึ่งตามตำราเบื้องต้น ซึ่งทำให้ทุกใบเต็มราวครึ่งเดียวแล้วต้องใช้ใบมากขึ้นเท่าตัว
ความสูงของ B+tree จึงไม่ได้เป็นฟังก์ชันของจำนวนแถวอย่างเดียว มันเป็นฟังก์ชันของ fill factor ในใบด้วย ใบที่เต็มครึ่งเดียวแปลว่าต้องใช้ใบเป็นสองเท่า และสองเท่านั้นดันชั้นบนขึ้นมาอีกชั้น
ราคาของการตัดท้ายคือมันได้ผลเฉพาะตอนที่คีย์เข้ามาเรียงแล้ว ซึ่งเป็นจริงตรงนี้เพราะแถวถูกเขียนเรียงตาม placed_at มาตั้งแต่บท 1 ถ้าคีย์เข้ามาสลับไปมา เงื่อนไข pos == n แทบไม่เป็นจริงเลย และผลลัพธ์จะไหลกลับไปหาแบบหั่นครึ่ง
ต้นไม้แบบตัดท้ายถูกเขียนลง file จริงได้ 493 หน้า เท่ากับ 2,019,328 byte ที่มากกว่า 492 อยู่หนึ่งหน้าคือหน้าที่ 0 ซึ่งเก็บ meta สามค่าคือเลขหน้าของราก ความสูง และจำนวนรายการ
ตัวเลข 15.6 % ในตารางข้างบนคือ 492 หน้าของ node ทั้งต้นเทียบกับ heap 3,153 หน้า และหน้า meta ที่เพิ่มมาอีกหนึ่งหน้าก็ไม่ทำให้สัดส่วนนั้นขยับ ที่ index กินน้อยขนาดนี้ทั้งที่ทำให้ครบทุกแถว เพราะใบเก็บแค่คีย์ 4 byte กับ record id 6 byte ไม่ได้เก็บตัวแถว
point lookup — จาก 3,153 หน้าเหลือ 3
หัวข้อที่มีชื่อว่า “point lookup — จาก 3,153 หน้าเหลือ 3”การเปิดต้นไม้กลับจาก file จริงผ่านตัวนับหน้า แล้ววัดว่าการค้นค่าเดียวแตะกี่หน้า
ต้นไม้ที่สร้างเสร็จอยู่ในหน่วยความจำ ซึ่งนับหน้าไม่ได้ จึงต้องเขียนลง file ก่อน แล้วเปิดกลับผ่าน Pager ตัวเดียวกับที่บท 2 ใช้นับ
ตัวสร้างของ BPlusTreeReader อ่านหน้าที่ 0 เพื่อเอา meta ออกมา แล้วรีเซ็ตตัวนับกลับเป็นศูนย์ทันที เพื่อไม่ให้หน้า meta ปนเข้าไปในตัวเลขที่บทนี้รายงาน
def _descend(self, key): """ลงจากรากถึงใบซ้ายสุดที่อาจมีคีย์นี้ (right=False เพื่อไม่ข้ามตัวซ้ำ)""" pno = self.root while True: page = self.pager.read_page(pno) is_leaf, n, _ = header(page) if is_leaf: return pno, page pno = inner_child(page, inner_search(page, n, key, right=False))
def range(self, lo, hi): """คืน [(key, (pageno, slot))] ของคีย์ในช่วง [lo, hi] เดินตามโซ่ใบ""" pno, page = self._descend(lo) out = [] i = leaf_search(page, header(page)[1], lo, right=False) while True: _, n, nxt = header(page) while i < n: k = leaf_key(page, i) if k > hi: return out out.append((k, leaf_rid(page, i))) i += 1 if nxt == NO_NEXT: return out pno, i = nxt, 0 page = self.pager.read_page(pno)
def lookup(self, key): return [rid for _, rid in self.range(key, key)]การค้นค่าเดียวไม่ได้เขียนแยก มันคือการค้นช่วงที่ขอบล่างกับขอบบนเป็นค่าเดียวกัน จึงใช้ทางเดินชุดเดียวกันทั้งหมด
ทุกครั้งที่ code เรียก self.pager.read_page ตัวนับเพิ่มหนึ่ง นี่คือหน่วยเดียวกับที่บท 1 ตกลงไว้ และเป็นตัวเลขที่ผู้อ่านรันเองแล้วต้องได้เท่ากัน
ค้นคีย์ placed_at = 1747119566 ซึ่งมีอยู่ 1 แถว ได้ผลแบบนี้
| ขั้น | หน้าที่แตะ |
|---|---|
| เดินจากรากลงถึงใบ | 2 หน้า |
| ตามไปหยิบแถวจาก heap | 1 หน้า |
| รวม | 3 หน้า |
| ถ้าไม่มี index ต้องอ่านทั้ง heap | 3,153 หน้า |
3 เทียบ 3,153 คือแตะหน้าน้อยกว่า 1,051 เท่า และแถวที่ได้ตรงกับการอ่านทั้งตารางแล้วกรองเองทุกประการ
เลข 2 ฝั่ง index ไม่ใช่ค่าที่ตั้งไว้ มันคือความสูงของต้นไม้พอดี เพราะ _descend อ่านหน้าละครั้งลงไปทีละชั้นจนถึงใบ
flowchart TD
R["ชั้น 0 · ราก 1 node · 490 separator key"]
R --> L1["ใบที่ 1"]
R --> L2["ใบที่ 2 · ใบที่คีย์ตกลงมา"]
R --> L3["ใบที่ 3"]
R --> LN["ใบที่ 491"]
L1 -. leaf chain .-> L2
L2 -. leaf chain .-> L3
L3 -. leaf chain .-> LN
L2 --> H["หน้าใน heap ที่ record id ชี้ไป"]
classDef hit stroke-width:3px
class R,L2,H hit
คำบรรยายภาพ: เส้นทึบคือทางที่ point lookup เดิน คือราก 1 หน้า แล้วลงใบอีก 1 หน้า รวมฝั่ง index 2 หน้า แล้วตามตัวชี้ไปหยิบแถวจาก heap อีก 1 หน้า รวม 3 หน้า · เส้นประคือ leaf chain ที่ร้อยใบทั้ง 491 ใบต่อกันตามลำดับคีย์ ซึ่ง point lookup ไม่ได้ใช้ แต่หัวข้อถัดไปใช้
ตัวเลขทั้งหมดนี้นับภายใต้เงื่อนไขเดียวกับสองบทก่อน คือยังไม่มี buffer pool ตัวอ่านหน้าจึงเรียกอ่านใหม่ทุกครั้ง record id หนึ่งตัวจึงเท่ากับหนึ่งหน้าเสมอ ซึ่งเป็นขอบบน
ส่วนตัวเลขฝั่ง heap ในหัวข้อถัดไปพิมพ์เป็นหน้าที่ไม่ซ้ำ จึงเป็นขอบล่างของกรณีที่ cache ได้ทั้งหมด และของจริงอยู่ระหว่างสองค่านั้น เป็นกติกาคู่แบบเดียวกับที่บท 2 ใช้
range scan — เดินตาม leaf chain ไม่ต้องกลับขึ้นราก
หัวข้อที่มีชื่อว่า “range scan — เดินตาม leaf chain ไม่ต้องกลับขึ้นราก”ผลวัดของการถามช่วงหนึ่งวันสองครั้งบนวันที่ปริมาณต่างกันมาก การแยกว่าหน้าที่แตะไปตกที่ฝั่ง index หรือฝั่ง heap และเชิงอรรถว่าตัวเลขฝั่ง heap สวยเพราะแถวเรียงอยู่แล้ว
ทุกใบเก็บเลขหน้าของใบถัดไปไว้ในหัวของตัวเอง ตัวชี้ชุดนี้คือ leaf chainleaf chainตัวชี้ที่ร้อยใบของ B+tree ต่อกันตามลำดับคีย์ ทำให้การอ่านเป็นช่วงเดินจากใบหนึ่งไปใบถัดไปได้เลย โดยไม่ต้องย้อนกลับขึ้นไปที่ราก และมันทำให้การอ่านเป็นช่วงเดินจากใบหนึ่งไปใบถัดไปได้เลย โดยไม่ต้องย้อนขึ้นไปที่รากทุกครั้ง
ใน range จะเห็นว่าหลังเดินลงถึงใบแรกแล้ว ลูปที่เหลือไม่แตะรากอีกเลย มันวนอ่านใบตาม nxt จนกว่าจะเจอคีย์ที่เกินขอบบน หรือจนกว่าจะหมดโซ่
ถามช่วงหนึ่งวันสองครั้ง บนวันที่ปริมาณต่างกันมาก ได้ผลแบบนี้
| ช่วงที่ถาม | แถวที่คืนมา | index แตะ | heap แตะ (หน้าที่ไม่ซ้ำ) | รวม |
|---|---|---|---|---|
| วันที่ 90 (วันธรรมดา) | 1,017 | 5 หน้า (ลงจากราก 2 + เดินตาม leaf chain 3) | 17 หน้า | 22 หน้า |
| วันที่ 140 (วันโปรโมชัน) | 17,603 | 45 หน้า (ลงจากราก 2 + เดินตาม leaf chain 43) | 279 หน้า | 324 หน้า |
ทั้งสองแถวเทียบกับการอ่านทั้ง heap 3,153 หน้า และทั้งสองแถวให้คำตอบตรงกับการอ่านทั้งตารางแล้วกรองเองทุกประการ
เลข 17 กับ 279 คือหน้าที่ไม่ซ้ำกัน ซึ่งเป็นขอบล่างตามกติกาคู่ที่ประกาศไว้ข้างบน ถ้าไล่ตาม record id ทีละตัวโดยไม่มี buffer pool เลย วันที่ 90 จะขออ่าน 1,017 ครั้งและวันที่ 140 จะขออ่าน 17,603 ครั้ง ของจริงอยู่ระหว่างสองค่านั้น
จุดที่น่าดูอยู่ในแถวล่าง ฝั่ง index จ่ายไป 45 หน้า ส่วนฝั่ง heap จ่ายไป 279 หน้าไม่ซ้ำ นั่นคือราว 86 % ของงานทั้งหมดไม่ได้อยู่ที่โครงสร้างที่เราเพิ่งสร้าง แต่อยู่ที่การไล่ตามตัวชี้กลับไปอ่านแถวจริง
ข้อสังเกตนี้คือรากของแนวคิด covering index ซึ่งเป็นเรื่องของ 🔁 บท 6 ถ้าคำตอบที่ต้องการอยู่ในใบครบอยู่แล้ว 279 หน้านั้นก็ไม่ต้องจ่าย
เชิงอรรถที่ต้องอ่านคู่กับตัวเลขข้างบน
หัวข้อที่มีชื่อว่า “เชิงอรรถที่ต้องอ่านคู่กับตัวเลขข้างบน”ตัวเลขฝั่ง heap ทั้ง 17 และ 279 สวยผิดปกติ เพราะแถวถูกเขียนเรียงตาม placed_at มาตั้งแต่ตอนสร้างข้อมูล แถวของวันเดียวกันจึงกองติดกันอยู่ไม่กี่หน้า
เปลี่ยนไปถามด้วยค่าที่ไม่ได้เรียงตามหน้า เช่น customer_id = 995 แล้วภาพกลับด้าน 97 แถวของลูกค้ารายนี้กระจายอยู่บน 93 หน้า คิดเป็น 0.96 หน้าต่อแถว
วางสองอัตราไว้ข้างกัน วันที่ 90 ได้ 1,017 แถวจาก 17 หน้า ส่วนลูกค้ารายนี้ได้ 97 แถวจาก 93 หน้า สองอัตราบนตารางเดียวกันนี้ห่างกันเกือบ 60 เท่า
เกือบหนึ่งหน้าต่อหนึ่งแถวคือค่าสูงสุดที่อัตรานี้ไปได้เมื่อนับหน้าไม่ซ้ำ แถวที่หยิบมาแทบไม่มีคู่ไหนอยู่หน้าเดียวกันเลย และเป็นเหตุผลว่าทำไม index ไม่ได้ถูกกว่าเสมอ
ลำดับที่ตรงกันระหว่าง index กับ heap ในบทนี้เป็นเรื่องบังเอิญของข้อมูลชุดนี้ ไม่ใช่สมบัติของ B+tree ชื่อเรียกของสมบัติข้อนี้กับราคาของมันเป็นเรื่องของบท 5
ถ้าแถวเยอะกว่านี้ ต้นไม้จะสูงแค่ไหน
หัวข้อที่มีชื่อว่า “ถ้าแถวเยอะกว่านี้ ต้นไม้จะสูงแค่ไหน”การยืดจำนวนแถวขึ้นสามระดับด้วยเลขคณิตของ fanout ที่วัดได้ และเพดานของต้นไม้ 3 ชั้น
คำถามที่ตามมาทันทีคือตัวเลข 3 หน้าอยู่ได้ถึงข้อมูลขนาดไหน ตอบได้ด้วยฟังก์ชันสั้นๆ ที่ไล่หารจำนวนใบด้วย fanout จนเหลือ node เดียว
def height_for(nrows, leaf_cap, fanout): leaves = max(1, -(-nrows // leaf_cap)) h, c = 1, leaves while c > 1: c = -(-c // fanout) h += 1 return h, leavesป้อนค่าที่วัดได้จริงเข้าไป คือใบรับได้ 408 รายการและ fanout 511 ได้ตารางนี้
| จำนวนแถว | ความสูง | จำนวนใบ | point lookup ฝั่ง index |
|---|---|---|---|
| 200,000 | 2 ชั้น | 491 หน้า | 2 หน้า |
| 1,000,000 | 3 ชั้น | 2,451 หน้า | 3 หน้า |
| 10,000,000 | 3 ชั้น | 24,510 หน้า | 3 หน้า |
| 100,000,000 | 3 ชั้น | 245,099 หน้า | 3 หน้า |
จากแถวบนสุดถึงแถวล่างสุด ข้อมูลโตจาก 200,000 แถวเป็น 100,000,000 แถว แต่จำนวนหน้าที่แตะฝั่ง index ขยับจาก 2 เป็น 3 เท่านั้น
เหตุผลอยู่ในการคูณสามตัว ต้นไม้ 3 ชั้นมีรากที่แตกได้ 511 ทาง แต่ละทางเป็น node ที่แตกได้อีก 511 ทาง และแต่ละใบรับได้ 408 รายการ เพดานจึงเป็น 511 × 511 × 408 เท่ากับ 106,537,368 แถว
คำว่า “ต้นไม้เตี้ย” จึงไม่ใช่คำเปรียบเปรย มันคือผลของการคูณเลขสามตัวนั้น
ตารางข้างบนเป็นกรณีดีที่สุดเพราะสมมติว่าใบเต็ม 408 รายการ ตารางจริงที่ผ่านการลบและแทรกสลับมาแล้วจะไม่เป็นแบบนั้น ลองตั้งใบเต็มที่ 70 % คือ 285 รายการ และ fanout 357 แล้วดูอีกรอบ
ที่ 200,000 แถวความสูงขยับจาก 2 เป็น 3 ชั้นทันที และที่ 100,000,000 แถวขยับเป็น 4 ชั้น กล่าวคือที่สองขนาดนี้ fill factor ที่ตกลงมาซื้อความสูงเพิ่มหนึ่งชั้น และ point lookup จ่ายเพิ่มหนึ่งหน้า ส่วนที่ 1,000,000 กับ 10,000,000 แถว ความสูงยังเป็น 3 ชั้นเท่าเดิมทั้งสองสมมติฐาน
คีย์ของคอร์สนี้เป็น <I> ตัวเดียวกว้าง 4 byte ส่วน index ของฐานข้อมูลจริงมักเก็บคีย์ประกอบเพื่อให้แถวที่คีย์ซ้ำกันยังเรียงกันได้แน่นอน
ถ้าเปลี่ยนไปเก็บคีย์ประกอบกว้าง 8 byte รายการในใบจะโตจาก 10 byte เป็น 14 byte และ fanout ตกจาก 511 เหลือ 341 คือ 1.50 เท่า ไม่ใช่ครึ่งหนึ่งอย่างที่คีย์กว้างขึ้นเท่าตัวชวนให้คิด เพราะตัวชี้ลูก 4 byte ในโหนดในไม่ได้โตตามคีย์ไปด้วย
สิ่งที่ยกไปใช้กับ index ตัวอื่นได้คือวิธีคำนวณ ไม่ใช่ตัวเลข 408 กับ 511
สิ่งที่บทนี้ยังตอบไม่ได้
หัวข้อที่มีชื่อว่า “สิ่งที่บทนี้ยังตอบไม่ได้”คำถามที่ตัวเลขในบทนี้เปิดทิ้งไว้ และหน้าที่ของสองบทถัดไป
บทนี้วัดสองกรณีสุดขั้วไว้แล้วบนตารางเดียวกัน คือ 3 หน้าสำหรับหนึ่งแถวที่ตอบด้วยการลงจากรากครั้งเดียว กับ 93 หน้าสำหรับ 97 แถวที่กระจายอยู่คนละหน้าเพราะคีย์ที่ถามไม่ได้เรียงตามหน้า
คำถามที่ยังไม่มีคำตอบคือเส้นแบ่งระหว่างสองกรณีนั้นอยู่ตรงไหน และเอนจินจะรู้ได้อย่างไรว่าคำถามที่มาถึงอยู่ฝั่งไหนของเส้น ทั้งที่มันยังไม่ได้อ่านข้อมูลสักแถว
บท 4 แก้ครึ่งแรกด้วยการเดาจำนวนแถวจากสถิติที่เก็บไว้ล่วงหน้า ส่วนบท 5 แก้ครึ่งหลังด้วยการตั้งราคาให้แต่ละแบบของการอ่าน แล้วประกาศหน่วยของต้นทุนที่ไม่มีวินาทีเข้ามาเกี่ยว
ส่วนที่บทนี้ยืนยันได้แล้วมีข้อเดียว คือจำนวนหน้าที่แตะฝั่ง index ของการค้นค่าเดียวแทบไม่โตตามขนาดข้อมูล ขณะที่ฝั่ง heap ยังโตตามจำนวนแถวที่คืน และจำนวนหน้าของการอ่านทั้งตารางโตตามตรงๆ ทุกแถว
สิ่งที่ประกอบขึ้นในบทนี้เป็นของเล่นที่ไว้อธิบายว่าทำไมแผนของ SQLite ถึงหน้าตาแบบนั้น ไม่ใช่ของที่เร็วกว่าหรือแทน SQLite ได้
- SQLite Database File Format — หัวข้อ B-tree Pages (ตรวจ 2026-08-11) — โครงของหน้า B-tree ในของจริง ทั้งการแยก interior page กับ leaf page และการวาง cell pointer array ในหน้า เป็นที่มาของการที่คอร์สนี้ตรึงหน้าไว้ที่ 4096 byte เท่ากับ
page_sizeของ file SQLite ที่บท 8 เอามาเทียบ - Alex Petrov, Database Internals (O’Reilly, 2019 — ISBN 978-1-4920-4034-7) บท 2–4 — การอ่านต่อสำหรับ B-tree bulk loading, นโยบายแตกหน้า และการวางโครงหน้าบน disk ซึ่งเป็นสามเรื่องที่บทนี้ทำแบบย่อที่สุดเท่าที่จะย่อได้
เช็กความเข้าใจ — บทที่ 3
ข้อ 1 / 3ทำไม fanout ของ B+tree ในบทนี้ถึงเป็น 511 ทาง