B-Trees: โครงสร้างข้อมูลที่บรรจุข้อมูลไว้มากกว่าที่คิด

 (benjamincongdon.me)
20 คะแนน โดย GN⁺ 2025-01-05 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • เมื่อไม่นานมานี้ได้อ่าน Database Internals ของ Alex Petrov และได้พบกับเนื้อหาเกี่ยวกับวิธีการสร้าง storage engine ของ DBMS โดยเฉพาะการปรับแต่งโครงสร้างข้อมูล B-Tree
  • ตอนเรียน B-Tree ในมหาวิทยาลัยเคยเข้าใจมันแบบง่าย ๆ ว่าเป็นแค่ “BST ที่ดีกว่า” จึงยังไม่ค่อยเห็นภาพว่าทำไมถึงถูกนำมาใช้งานจริง
  • B-Tree เหมาะกับการเก็บข้อมูลขนาดใหญ่และค้นหาได้รวดเร็วโดยคำนึงถึง disk I/O
  • บทความนี้อธิบายว่าทำไม B-Tree จึงจำเป็น ทำงานอย่างไร และสามารถปรับแต่งอะไรได้บ้างในการใช้งานจริง
  • จุดเด่นสำคัญคือการรวมคีย์จำนวนมากไว้ในโหนดเดียวเพื่อลดจำนวนครั้งในการเข้าถึงดิสก์

ข้อจำกัดที่เกิดจากดิสก์

  • สมมติสถานการณ์ที่ข้อมูลทั้งหมดไม่สามารถอยู่ในหน่วยความจำได้
  • ดิสก์มีคุณสมบัติที่อ่านและเขียนทีละ page
  • การเข้าถึงดิสก์ช้ากว่าการเข้าถึงหน่วยความจำมาก
  • ดังนั้นโครงสร้างข้อมูลจึงต้องจัดวางข้อมูลโดยยึด page เป็นศูนย์กลาง และต้องเปรียบเทียบคีย์ให้ได้มากที่สุดด้วยการเข้าถึงดิสก์ให้น้อยที่สุด
  • หากเก็บ BST ลงบนดิสก์ตรง ๆ โหนดจะกระจัดกระจาย ทำให้จำนวนครั้งที่เข้าถึงดิสก์เพิ่มตามจำนวนครั้งที่ค้นหา
  • B-Tree รวบรวมหลายคีย์ไว้ในโหนดเดียว เพื่อให้การอ่านดิสก์หนึ่งครั้งสามารถเปรียบเทียบคีย์ได้หลายตัว

Slot page

  • เมื่อต้องจัดวางข้อมูลลงดิสก์ จะจัดการเป็นหน่วย “page”
  • แต่ละ page มี header, cell ที่เก็บข้อมูลความยาวแปรผัน และอาร์เรย์ของ offset pointer ที่เก็บตำแหน่งของ cell
  • โครงสร้าง slot page มีข้อดีคือแม้ขนาดคีย์จะไม่คงที่ ก็ยังรักษาลำดับการเรียงได้โดยไม่ต้องเสียภาระกับการจัดเรียงข้อมูลใหม่มากนัก
  • เวลาลบหรือแทรกคีย์ การจัดเรียงเฉพาะ pointer ใหม่มีประสิทธิภาพกว่าการย้ายข้อมูลจริงมาก
  • ตัวอย่างเช่น SQLite ใช้ free list ภายในโครงสร้าง page ลักษณะนี้เพื่อรีไซเคิลพื้นที่ของ cell ที่ถูกลบ

การค้นหาใน B-Tree

  • อัลกอริทึมการค้นหาใน B-Tree นั้นเรียบง่าย:
    1. เริ่มจากโหนดราก
    2. ดู Separator Key ของโหนดปัจจุบันเพื่อหาโหนดลูกที่คาดว่าน่าจะมีคีย์ที่ค้นหา
    3. สำรวจต้นไม้แบบเรียกซ้ำ
    4. หากพบโหนดใบที่มีคีย์ที่ค้นหาให้จบการทำงาน ถ้าไม่พบให้สรุปว่าไม่มีอยู่
  • ใน internal node อาจเก็บแค่ Separator Key แทนข้อมูลจริง ส่วนข้อมูลจริงมักเก็บไว้เฉพาะใน leaf node
  • เพื่อให้ค้นหาคีย์ภายในโหนดได้อย่างมีประสิทธิภาพด้วย binary search คีย์ในแต่ละโหนดจึงถูกเก็บให้เรียงลำดับไว้เสมอ

การย่อ Separator Key

  • Separator Key ของ internal node ไม่จำเป็นต้องเก็บคีย์จริงทั้งหมด แค่พอสำหรับแบ่งช่วงก็เพียงพอ
  • ตัวอย่างเช่น หากต้องแบ่งช่วงระหว่าง 0xAAAAAA กับ 0xBBBBBB ก็ไม่จำเป็นต้องเก็บ 0xBBBBBB ทั้งหมด แต่อาจใช้เพียง prefix ที่สั้นกว่าก็แยกได้
  • ในฐานข้อมูลที่มีคีย์ยาวมาก การย่อแบบนี้ช่วยประหยัดพื้นที่จัดเก็บได้มาก
  • นอกจากการย่อ Separator Key แล้ว ยังมีกลยุทธ์ลดขนาด prefix และ suffix อย่างมีประสิทธิภาพด้วย
  • เนื่องจาก leaf node มีจำนวนมากกว่ามาก จึงมีมุมมองว่าการบีบอัด prefix ช่วยด้านประสิทธิภาพได้มากกว่า

Overflow page

  • เมื่อโหนดหนึ่งมีคีย์มากเกินกว่าจะใส่ใน page เดียวได้ จะใช้ overflow page
  • แทนที่จะย้ายคีย์ทั้งหมดไปไว้ใน overflow page จะเก็บเพียง prefix สั้น ๆ ไว้ในโหนด และแยกส่วนที่เหลือไปเก็บต่างหาก
  • วิธีนี้ทำให้เวลาตรวจสอบว่ามีคีย์อยู่หรือไม่ หรือเวลาค้นหาแบบช่วง สามารถเช็ก prefix ในโหนดก่อน และอ่าน overflow page เฉพาะเมื่อจำเป็นจริง ๆ
  • เป็นแนวทางที่แม้จะต้องจัดสรร page เพิ่ม แต่ช่วยลดต้นทุนการค้นหาโดยรวมได้

Sibling pointer

  • มีแนวทางการติดตั้ง pointer ไปยังโหนดพี่น้องทางซ้ายและขวาระหว่างโหนด
  • วิธีนี้ช่วยให้เวลาค้นหาแบบช่วง สามารถกระโดดจาก leaf node หนึ่งไปยังโหนดพี่น้องได้ทันที และไล่สำรวจคีย์ต่อเนื่องได้รวดเร็ว
  • หากไม่มี sibling pointer จะต้องย้อนกลับขึ้นไปยังโหนดแม่แล้วลงมาใหม่ซ้ำ ๆ ทำให้ต้นทุน I/O สูงขึ้น
  • เนื่องจากช่วงคีย์ของโหนดพี่น้องไม่ทับซ้อนกัน การเลื่อนไปตาม right sibling pointer จึงรับประกันได้ว่าเป็น “ช่วงคีย์ถัดไป”

รูปแบบดัดแปลงของ B-Tree

  • นอกจาก B⁺-Tree ยังมีโครงสร้างแบบดัดแปลงอีกหลายแบบ
  • “Lazy B-Tree” อย่าง WiredTiger หรือ Lazy-Adaptive Tree ใช้วิธีบัฟเฟอร์การเขียนเพื่อเพิ่มประสิทธิภาพ
  • FD-Tree เป็นโครงสร้างที่ออกแบบให้เหมาะกับคุณลักษณะของ SSD โดยคำนึงถึงข้อจำกัดทางกายภาพ เช่น การเขียนเป็นบล็อก
  • Bw-Tree(Buzzword Tree) เป็นโครงสร้างข้อมูลที่เหมาะกับการเข้าถึง tree ในหน่วยความจำและรองรับ concurrency สูง

บทสรุป

  • ระหว่างแนวคิดเชิงนามธรรมของ “B⁺-Tree” กับการนำไปใช้จริงอย่าง “DB format ของ SQLite” มีความแตกต่างทั้งในด้านการปรับแต่งและรายละเอียดการติดตั้งจำนวนมาก
  • การปรับแต่งเหล่านี้ไม่ได้เปลี่ยน Big-O complexity แต่ส่งผลอย่างมากต่อประสิทธิภาพและการใช้งานของฐานข้อมูลในสภาพแวดล้อมจริง
  • นอกเหนือจากสิ่งที่กล่าวถึงที่นี่ ระบบ storage แต่ละแบบยังต้องการการจูนละเอียดเฉพาะทางอีกมาก
  • เบื้องหลังคำว่า “ต้องการข้อมูลประกอบเพิ่มอีกนิดหน่อย” ซ่อนความซับซ้อนของการพัฒนาและความยากในการดีบักไว้
  • ตัวอย่างภาพ B-Tree ที่วาดให้ใกล้เคียงของจริงมากขึ้นซึ่งน่าประทับใจ คือไดอะแกรม B-Tree ใน Designing Data Intensive Applications

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2025-01-05
ความเห็นจาก Hacker News

  • โครงสร้างของเพจประกอบด้วย header, cell และ offset pointer และมีข้อดีคือสามารถเก็บข้อมูลขนาดแปรผันได้

    • มีต้นทุนต่ำเพราะเพียงแค่จัดเรียงตำแหน่งของอาร์เรย์ pointer ใหม่
    • หากอาร์เรย์ pointer เรียงตามลำดับการจัดเรียงของคีย์ ตำแหน่งจริงของคีย์ภายในเพจก็ไม่สำคัญ

  • เป็นบทความที่ยอดเยี่ยมและมีแอนิเมชันเกี่ยวกับ B-tree รวมอยู่ด้วย

  • เมื่อหลายปีก่อนได้ implement B-link Tree ที่รองรับ concurrent recovery โดยอิงจากงานวิจัยของ Ibrahim Jaluta

  • ได้ทำ SQLite disk page explorer ขึ้นมา จึงเข้าใจ B-tree ได้ดียิ่งขึ้น

  • แม้จะไม่มีเนื้อหาเกี่ยวกับ B-link tree, concurrency และ locking แต่ข้อมูลเหล่านั้นอาจมากเกินความจำเป็น

  • ความเห็นเก่า: Hacker News

  • เป็นบทความที่ยอดเยี่ยมและอธิบายความสำคัญของรายละเอียดได้ดี

    • อยากเห็นบทความเพิ่มเติมที่เปรียบเทียบ LSM-Tree กับ B-Tree และ LSM-Tree ระหว่างกัน

  • เป็นแหล่งข้อมูลที่ดีเกี่ยวกับการ implement B-tree ด้วย Golang

  • เป็นแฟนตัวยงของบทความนี้ และก่อนหน้านี้ก็มี 'ความเข้าใจแบบคลุมเครือ' คล้ายกับผู้เขียน

    • เป็นแหล่งข้อมูลที่ยอดเยี่ยมสำหรับคนที่อยากทำให้ mental model ของตัวเองชัดเจนขึ้น