B-tree และดัชนีฐานข้อมูล

B-tree คืออะไร?

• B-tree เป็นโครงสร้างพื้นฐานสำคัญของซอฟต์แวร์จำนวนมาก โดยเฉพาะระบบจัดการฐานข้อมูล (DBMS)

• MySQL, Postgres, MongoDB, Dynamo และระบบอื่น ๆ พึ่งพา B-tree เพื่อให้การดึงข้อมูลมีประสิทธิภาพผ่าน ดัชนี

• เนื้อหานี้จะอธิบายว่า B-tree และ B+tree ทำงานอย่างไร เหตุใดฐานข้อมูลจึงใช้สิ่งเหล่านี้กับดัชนี และทำไมการใช้ UUID เป็นคีย์หลักอาจเป็นความคิดที่ไม่ดี

• B-tree เก็บคู่ข้อมูลที่เรียกว่า คีย์ และ ค่า ไว้ในสิ่งที่โปรแกรมเมอร์เรียกว่าโครงสร้างคล้ายต้นไม้

• B-tree ประกอบด้วย โหนด (สี่เหลี่ยม) และ ตัวชี้ลูก (เส้นที่เชื่อมโหนด)

• โหนดบนสุดเรียกว่า โหนดราก โหนดระดับล่างสุดเรียกว่า โหนดใบ และโหนดอื่นทั้งหมดเรียกว่า โหนดภายใน

• ด้านล่างคือคำนิยามของ B-tree:

  • แต่ละโหนดเก็บคู่คีย์/ค่าได้ N คู่ (โดยที่ N มากกว่า 1 และไม่เกิน K)
  • แต่ละโหนดภายในมีคู่คีย์/ค่าอย่างน้อย N/2 คู่ (โหนดภายในคือโหนดที่ไม่ใช่ใบหรือราก)
  • แต่ละโหนดมีลูก N+1 ตัว
  • โหนดรากต้องมีค่าอย่างน้อยหนึ่งค่าและมีลูกสองตัว เว้นแต่จะเป็นโหนดเดียวในต้นไม้
  • โหนดใบทั้งหมดอยู่ในระดับเดียวกัน

• คุณสมบัติสำคัญอีกอย่างของ B-tree คือการเรียงลำดับ โดยองค์ประกอบภายในแต่ละโหนดจะถูกเก็บตามลำดับ

• ด้วยคุณสมบัตินี้ จึงสามารถ ค้นหาคีย์ ได้อย่างมีประสิทธิภาพมาก โดยเริ่มจากโหนดรากแล้ว:

  1. ตรวจสอบว่าคีย์ที่ต้องการค้นหาอยู่ในโหนดหรือไม่
  2. หากไม่อยู่ และหากกำลังจะเพิ่มคีย์ ให้หาตำแหน่งที่คีย์ควรถูกแทรกในโหนด
  3. จากจุดนี้ให้ตาม ตัวชี้ลูก ลงไปยังระดับถัดไปและทำขั้นตอนซ้ำ

• เมื่อค้นหาแบบนี้ เราจำเป็นต้องเยี่ยมเพียง หนึ่ง โหนดต่อหนึ่งระดับของต้นไม้เพื่อค้นหาคีย์เดียว

• B-tree ถูกออกแบบมาเป็นพิเศษให้ทำงานได้ดีกับข้อมูลปริมาณ มหาศาล ที่ต้องคงอยู่ในสตอเรจระยะยาว (ดิสก์) เพราะแต่ละโหนดใช้จำนวนไบต์คงที่

• จำนวนค่าที่แต่ละโหนดเก็บได้ใน B-tree จะแตกต่างกันไปตามจำนวนไบต์ที่จัดสรรให้โหนดนั้น และจำนวนไบต์ที่คู่คีย์/ค่าแต่ละคู่ใช้ไป

B+tree (ที่ปรับให้เหมาะกับฐานข้อมูล)

• B+tree คล้ายกับ B-tree แต่มีการเปลี่ยนกฎดังนี้:
  • เก็บคู่คีย์/ค่าไว้เฉพาะในโหนดใบ
  • โหนดที่ไม่ใช่ใบจะเก็บเฉพาะคีย์และตัวชี้ลูกที่เกี่ยวข้อง
• วิธีที่ MySQL ใช้ B+tree ในดัชนียังมีกฎเพิ่มเติมเฉพาะอีกสองข้อ:
  • โหนดที่ไม่ใช่ใบจะเก็บตัวชี้ลูก N ตัวแทนที่จะเป็น N+1
  • ทุกโหนดยังมีตัวชี้ "next" และ "previous" ด้วย ทำให้แต่ละระดับของต้นไม้ทำหน้าที่เป็น doubly linked list ได้เช่นกัน
• มีเหตุผลสองข้อที่ทำให้ B+tree เหมาะกับฐานข้อมูลมากกว่า:
  1. โหนดภายในไม่จำเป็นต้องเก็บค่า จึงใส่คีย์ได้มากขึ้นต่อหนึ่งโหนดภายใน ซึ่งช่วยลดความลึกของต้นไม้
  2. ค่า ทั้งหมดถูกเก็บไว้ในระดับเดียวกัน และสามารถไล่ตามลำดับได้ผ่าน linked list ของระดับล่างสุด

วิธีใช้ B+tree ใน MySQL

• MySQL รองรับ storage engine หลายแบบ และ engine ที่ใช้กันแพร่หลายที่สุดคือ InnoDB ซึ่งพึ่งพา B+tree อย่างมาก
• ที่จริงแล้ว InnoDB พึ่งพามันมากถึงขั้นเก็บ_ข้อมูลทั้งหมดของตาราง_ไว้ใน B+tree โดยใช้คีย์หลักของตารางเป็นคีย์ของต้นไม้
• ทุกครั้งที่สร้างตาราง InnoDB ใหม่ คุณต้องกำหนดคีย์หลัก
• MySQL จะสร้าง B+tree สำหรับแต่ละตารางใหม่ โดยค่าที่ตั้งเป็นคีย์หลักจะกลายเป็นคีย์ของต้นไม้ ส่วนค่าคือค่าคอลัมน์อื่นทั้งหมดของแต่ละแถวและจะถูกเก็บไว้เฉพาะในโหนดใบ
• ขนาดโหนดของ B+tree แต่ละโหนดนี้ตั้งค่าเริ่มต้นไว้ที่ 16k
• ทุกครั้งที่ MySQL ต้องเข้าถึงข้อมูลชิ้นหนึ่ง (เช่น คีย์หรือค่า) มันจะโหลดทั้งเพจที่เกี่ยวข้องทั้งหมด (โหนดของ B+tree) จากดิสก์ แม้ว่าจะไม่ต้องใช้คีย์หรือค่าอื่นในเพจนั้นก็ตาม
• การสร้างดัชนีรองบนตาราง InnoDB ก็เป็นเรื่องปกติเช่นกัน สำหรับดัชนีรองแต่ละตัวจะมี B+tree แบบ persistent เพิ่มเติมถูกสร้างขึ้น โดยคีย์คือคอลัมน์ที่ผู้ใช้เลือกมาสร้างดัชนี และค่าคือ คีย์หลัก ของแถวที่เชื่อมโยงกัน

การเลือกคีย์หลัก: การแทรกข้อมูล

• วิธีที่ข้อมูลในตารางถูกจัดวางใน B+tree จะแตกต่างกันไปตามคีย์ที่คุณเลือก ดังนั้นการเลือก PRIMARY KEY จึงส่งผลต่อเลย์เอาต์ของข้อมูลทั้งหมดบนดิสก์
• สองตัวเลือกที่มักใช้เป็นคีย์หลักคือ:
  • ลำดับจำนวนเต็ม (BIGINT UNSIGNED AUTO_INCREMENT เป็นต้น)
  • UUID (ซึ่งมีหลายเวอร์ชัน)
• หากใช้คีย์หลักแบบ UUIDv4 ผลลัพธ์เมื่อแทรกข้อมูลคือ:
  1. ไม่สามารถคาดเดาได้ล่วงหน้าว่าจะต้องเข้าไปยังโหนดใดเพื่อแทรก
  2. ไม่สามารถคาดเดาโหนดใบเป้าหมายสำหรับการแทรกได้
  3. ค่า ในโหนดใบจะไม่ถูกเรียงลำดับ
• ปัญหาข้อ 1 และ 2 เกิดจากการที่ต้องเข้าเยี่ยมหลายโหนด (เพจ) ทั่วทั้งต้นไม้ระหว่างการแทรกจำนวนมาก การอ่านและเขียนที่มากเกินไปนี้ทำให้ประสิทธิภาพลดลง
• หากใช้ BIGINT UNSIGNED AUTO_INCREMENT เป็นคีย์หลัก:
  1. เมื่อแทรกค่าใหม่ จะเดินตามเส้นทางด้านขวาสุดเสมอ
  2. โหนดใบจะถูกเพิ่มเฉพาะทางด้านขวาของต้นไม้
  3. ในระดับโหนดใบ ข้อมูลจะถูกเรียงตามลำดับที่แทรก
• ด้วยเหตุผลในข้อ 1 และ 2 การแทรกแบบต่อเนื่องจำนวนมากจะกลับมาใช้เส้นทางเพจเดิมซ้ำ ๆ จึงช่วยลดคำขอ I/O เมื่อต้องแทรกคู่คีย์/ค่าจำนวนมาก

การเลือกคีย์หลัก: การอ่านข้อมูลตามลำดับ

• การดึงข้อมูลตามลำดับเวลาเป็นสิ่งที่พบได้บ่อยในฐานข้อมูล
• หากใช้ UUIDv4 เป็นคีย์หลัก ลำดับค่าของผลลัพธ์ที่ค้นหาจะกระจายอยู่ตามโหนดใบที่ไม่ต่อเนื่องหลายโหนด
• หากค้นหาค่าที่ถูกแทรกอย่างต่อเนื่อง เพจทั้งหมดที่มีผลลัพธ์จะอยู่ติดกัน และเมื่อดึงหลายแถว ผลลัพธ์ทั้งหมดอาจอยู่ติดกันภายในเพจเดียวด้วยซ้ำ
• สำหรับรูปแบบคิวรีแบบนี้ การใช้คีย์หลักแบบลำดับจะช่วยลดจำนวนเพจที่ต้องอ่านได้

การเลือกคีย์หลัก: ขนาด

• ขนาดของคีย์หลักก็เป็นสิ่งสำคัญที่ต้องพิจารณาเช่นกัน คีย์หลักควรจะ:
  1. ใหญ่พอที่จะไม่ใช้หมด
  2. เล็กพอที่จะไม่กินพื้นที่จัดเก็บมากเกินไป
• สำหรับลำดับจำนวนเต็ม ตารางขนาดเล็กอาจใช้ MEDIUMINT (ค่าไม่ซ้ำได้ 16 ล้านค่า) หรือ INT (ค่าไม่ซ้ำได้ 4 พันล้านค่า)
• สำหรับตารางขนาดใหญ่ ควรใช้ BIGINT เพื่อความปลอดภัย (มีค่าที่เป็นไปได้ประมาณ 18 quintillion ค่า) โดย BIGINT มีขนาด 64 บิต (8 ไบต์)
• UUID โดยทั่วไปมีขนาด 128 บิต (16 ไบต์) ซึ่งใหญ่กว่าชนิดจำนวนเต็มที่ใหญ่ที่สุดของ MySQL ถึงสองเท่า
• เนื่องจากโหนดของ B+tree มีขนาดคงที่ การใช้ BIGINT จึงทำให้ใส่คีย์ได้มากกว่า UUID ในหนึ่งโหนด ซึ่งนำไปสู่ต้นไม้ที่ตื้นกว่าและการค้นหาที่เร็วกว่า

B+tree, เพจ และ InnoDB

• ข้อดีอย่างหนึ่งของ B+tree คือคุณสามารถกำหนดขนาดโหนดได้ตามต้องการ
• ใน InnoDB โหนดของ B+tree มักตั้งเป็น 16k ซึ่งเป็นขนาดของ เพจ InnoDB
• ระหว่างการประมวลผลคิวรี (และดังนั้นรวมถึงการไล่ต้นไม้ B+tree) InnoDB จะไม่อ่านแถวหรือคอลัมน์เดี่ยว ๆ จากดิสก์ แต่จะโหลดทั้งเพจที่เกี่ยวข้องทุกครั้งที่ต้องเข้าถึงข้อมูลชิ้นใดชิ้นหนึ่ง
• InnoDB มีเทคนิคบางอย่างเพื่อบรรเทาปัญหานี้ โดยเทคนิคหลักคือ buffer pool ซึ่งเป็นแคชในหน่วยความจำสำหรับเพจ InnoDB ที่อยู่ระหว่างเพจบนดิสก์กับการรันคิวรีของ MySQL
• เมื่อ MySQL ต้องอ่านเพจ มันจะตรวจสอบก่อนว่าเพจนั้นอยู่ใน buffer pool แล้วหรือไม่ ถ้าอยู่ก็อ่านจากตรงนั้นและข้ามการทำงาน I/O กับดิสก์ หากไม่อยู่ก็จะไปหาเพจนั้นจากดิสก์ เพิ่มเข้าไปใน buffer pool แล้วจึงทำคิวรีต่อ
• buffer pool ช่วยเพิ่มประสิทธิภาพคิวรีได้_อย่างมหาศาล_ หากไม่มี buffer pool ระบบจะต้องทำงาน I/O กับดิสก์มากกว่านี้มากเพื่อรองรับเวิร์กโหลดของคิวรี

สถานการณ์อื่น ๆ

• แม้ที่นี่จะเน้นเปรียบเทียบคีย์แบบลำดับกับคีย์แบบสุ่ม/UUID เป็นหลัก แต่หลักการเหล่านี้ก็เป็นสิ่งที่ควรจำไว้ไม่ว่าคุณจะกำลังพิจารณาคีย์หลักหรือคีย์รองชนิดใดก็ตาม
• ตัวอย่างเช่น คุณอาจพิจารณาใช้ timestamp user.created_at เป็นคีย์ดัชนี ซึ่งมีคุณสมบัติคล้ายจำนวนเต็มแบบลำดับ กล่าวคือ ถ้าไม่ได้แทรกข้อมูลเก่าเข้าไป การแทรกมักจะไปตามเส้นทางด้านขวาสุดเสมอ
• ในทางกลับกัน สตริงอย่าง user.email_address จะมีคุณสมบัติคล้ายคีย์แบบสุ่มมากกว่า เพราะผู้ใช้ไม่ได้สร้างบัญชีตามลำดับตัวอักษรของอีเมล ดังนั้นการแทรกจึงกระจายไปทั่วทั้ง B+tree

สรุป

• เราได้พูดถึงหลายเรื่องเกี่ยวกับ B+tree, ดัชนี และการเลือกคีย์หลัก
• แม้ภายนอกจะดูเรียบง่าย แต่หากต้องการดึงประสิทธิภาพของฐานข้อมูลออกมาให้มากที่สุด ยังมีรายละเอียดปลีกย่อยที่ต้องพิจารณา
• หากอยากทดลองเพิ่มเติม ลองเข้าไปที่เว็บอินเทอร์แอกทีฟ B+tree

[GN⁺]

ความคิดเห็นบน Hacker News

• ใช้กลยุทธ์ดูแลวิกิให้ยังมีประโยชน์อยู่เสมอด้วยการจัดการแบบ B-Tree

  • ถ้าหน้าแลนดิ้งมีมากเกินไป ก็ย้ายลิงก์และย่อหน้าไปยังหน้าย่อย
  • ลิงก์ที่คล้ายกันและเก่าจะย้ายไปยังหน้าพี่น้องที่ตรงกับหัวข้อ
  • สุดท้ายเอกสารเก่าจะถูกย้ายลงไปสามระดับจากหน้าแลนดิ้ง
  • การทำเอกสารสุดท้ายแล้วก็กลับไปเป็นปัญหาเรื่องการค้นหา
  • เป็นวิธีที่ดีในการใช้เวลาบ่ายวันศุกร์ให้เกิดประสิทธิผล

• ตามหาสิ่งแบบนี้มานานแล้ว เป็นโพสต์ที่น่าทึ่งมาก

  • อยากให้มีส่วนที่พูดถึง composite index ด้วย

• ขอบคุณสำหรับภาพประกอบที่ยอดเยี่ยม

  • เคยทำงานด้านการรองรับการทำดัชนี BTree+ บน Aerospike
  • การลบคีย์ที่หมดอายุออกจาก BTree+ เป็นเรื่องท้าทาย
  • ตัดสินใจรวมการแตกกิ่งของหนึ่งระดับเฉพาะภายในโหนด leaf พี่น้องตัวแรกเท่านั้น
  • เพิ่ม sharding บน BTree+ เพื่อให้เร็วขึ้นและลด lock contention
  • ระหว่างกระบวนการเก็บกวาด BTree+ อาจเสียสมดุลได้
  • จึงมีฟีเจอร์ rebuild index เพื่อหลีกเลี่ยงงานเก็บกวาดเพิ่มเติม

• คุกกี้โมดัลใช้งานไม่ได้บน Firefox มือถือ

  • ควรให้ผู้ใช้ไปตั้งค่าได้จากในเบราว์เซอร์

• ไม่ควรใช้คอลัมน์ UUID เป็น primary key

  • ต้องคัดลอก int 128 บิตไปยังทุกด้านของความสัมพันธ์
  • ในกรณีส่วนใหญ่มันเป็นแบบสุ่มล้วน
  • สำหรับความสัมพันธ์ภายในตารางควรใช้ bigserial (64 บิต) PK และใช้ UUID (128 บิต) สำหรับตัวระบุระดับแอปพลิเคชันและ natural key
  • ฐานข้อมูลจะมีความสุขขึ้นมาก

• เป็นสื่อการสอนที่ยอดเยี่ยม

  • เดโมแบบอินเทอร์แอกทีฟลักษณะนี้ช่วยได้มาก

• ถ้าบล็อกดิสก์และโหนด B-Tree มีขนาด 16k และคีย์ ค่า และตัวชี้ลูกทั้งหมดเป็น 8 บิต ก็จะเก็บคีย์/ค่าได้ 682 คู่ต่อโหนด และตัวชี้ลูก 683 ตัว

  • ต้นไม้สามระดับสามารถเก็บคู่คีย์/ค่าได้มากกว่า 300 ล้านคู่
  • แต่ละองค์ประกอบควรมีขนาด 8 ไบต์

• เป็นบทความที่ยอดเยี่ยม

  • InnoDB เรียกการเก็บข้อมูลไว้ใน B-tree เองว่า clustered index
  • MyISAM เป็น non-clustered index
  • Oracle และตัวอื่น ๆ ให้เลือกได้

• มีคนถามว่า v0, v1, ...v10 ในกราฟหมายถึงอะไร

  • สงสัยว่าหมายถึงคนละหน้ากันหรือไม่

• เป็นภาพข้อมูลเชิงโต้ตอบที่สวยงาม

  • ยอดเยี่ยมมากทั้งในแง่การสอนและการทำให้เข้าถึงคนทั่วไป