วิธีการจัดทำดัชนีและการเข้าถึง

ดัชนีและวิธีการเข้าถึงเป็นโครงสร้างข้อมูลเสริม ซึ่งส่วนใหญ่เป็น B+-trees และดัชนีแฮช ที่ช่วยให้ฐานข้อมูลสามารถค้นหาทูเพิลที่ตรงกันได้โดยไม่ต้องสแกนทั้งตาราง ทำให้เกิดเส้นทางการเข้าถึงที่รวดเร็วซึ่งตัวปรับแต่งประสิทธิภาพ (optimizer) ใช้ประโยชน์

Definition

ดัชนีคือโครงสร้างข้อมูลเสริมบนแอตทริบิวต์หนึ่งหรือหลายแอตทริบิวต์ของความสัมพันธ์ที่แมปค่าคีย์ไปยังตำแหน่งของทูเพิลที่ตรงกัน ทำให้สามารถเรียกค้นข้อมูลได้ในเวลาที่น้อยกว่าเชิงเส้นเมื่อเทียบกับขนาดตาราง; วิธีการเข้าถึงคือกลไกที่การสอบถามใช้ในการอ่านข้อมูล เช่น การสแกนทั้งหมดหรือการสแกนดัชนี

Scope

หัวข้อนี้ครอบคลุมโครงสร้างและแนวคิดเบื้องหลังเส้นทางการเข้าถึงข้อมูล: ความแตกต่างระหว่างดัชนีแบบคลัสเตอร์และไม่คลัสเตอร์, ดัชนีหลักและดัชนีรอง; B+-tree ในฐานะดัชนีเรียงลำดับที่สำคัญซึ่งรองรับการค้นหาแบบเท่ากันและแบบช่วง; ดัชนีแบบแฮชสำหรับการค้นหาแบบเท่ากัน; และบทบาทของดัชนีในการเลือก, การรวม (join), และการหลีกเลี่ยงการจัดเรียง (sort avoidance) นอกจากนี้ยังกล่าวถึงว่าการเลือกดัชนีส่งผลต่อต้นทุนการสอบถามและค่าใช้จ่ายในการอัปเดตอย่างไร โดยไม่รวมการเลือกแผนโดยรวมของตัวปรับแต่งประสิทธิภาพที่อิงตามต้นทุน ซึ่งเป็นหัวข้อแยกต่างหาก

Core questions

• B+-tree รองรับการสอบถามทั้งแบบเท่ากันและแบบช่วงได้อย่างมีประสิทธิภาพได้อย่างไร?
• ความแตกต่างระหว่างดัชนีแบบคลัสเตอร์และไม่คลัสเตอร์, ดัชนีหลักและดัชนีรองคืออะไร?
• เมื่อใดที่ดัชนีแฮชดีกว่าดัชนีแบบต้นไม้?
• ดัชนีช่วยเร่งความเร็วในการเลือก, การรวม (joins), และการเรียกค้นข้อมูลแบบเรียงลำดับได้อย่างไร?
• ค่าใช้จ่ายในการบำรุงรักษาดัชนีภายใต้การแทรก, การอัปเดต, และการลบคืออะไร?

Key concepts

• ดัชนี B+-tree
• ดัชนีแฮช
• ดัชนีแบบคลัสเตอร์เทียบกับไม่คลัสเตอร์
• ดัชนีหลักและดัชนีรอง
• ดัชนีแบบหนาแน่นและแบบเบาบาง
• การค้นหาแบบช่วงและแบบเท่ากัน
• การแฮชแบบขยายได้และแบบเชิงเส้น
• ค่าใช้จ่ายในการบำรุงรักษาดัชนี

Key theories

ดัชนี B+-tree

B+-tree เป็นโครงสร้างต้นไม้ค้นหาแบบสมดุลที่มี fanout สูง ซึ่งเก็บคีย์ในลำดับที่จัดเรียงไว้ โดยมีการอ้างอิงข้อมูลทั้งหมดอยู่ในส่วนใบ; รองรับการสอบถามแบบเท่ากันและแบบช่วง และการสแกนแบบเรียงลำดับด้วย I/O แบบลอการิทึม และยังคงสมดุลภายใต้การแทรกและการลบ

ดัชนีแบบคลัสเตอร์เทียบกับไม่คลัสเตอร์

ดัชนีแบบคลัสเตอร์จะจัดเรียงแถวของตารางตามคีย์ดัชนีทางกายภาพ ทำให้การสแกนแบบช่วงมีประสิทธิภาพมาก ในขณะที่ดัชนีแบบไม่คลัสเตอร์ (รอง) จะชี้ไปยังไฟล์ที่ไม่ได้จัดเรียง ดังนั้นการเรียกค้นแถวที่ตรงกันจำนวนมากอาจมีค่าใช้จ่าย I/O หนึ่งครั้งต่อแถว

ดัชนีแฮช

ดัชนีแบบแฮชจะแมปคีย์ไปยังบัคเก็ตสำหรับการค้นหาแบบเท่ากันที่คาดว่าจะใช้เวลาคงที่ แต่ไม่รองรับการสอบถามแบบช่วง; แผนการแบบไดนามิก เช่น การแฮชแบบขยายได้และแบบเชิงเส้น ช่วยให้ดัชนีเหล่านี้เติบโตได้อย่างเหมาะสมกับข้อมูล

Clinical relevance

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

History

Bayer และ McCreight ได้นำเสนอ B-tree ในปี 1972 เพื่อรักษาดัชนีเรียงลำดับขนาดใหญ่บนดิสก์; B+-tree ซึ่งเป็นรูปแบบหนึ่งที่เก็บข้อมูลทั้งหมดไว้ในส่วนใบ (leaves) ได้กลายเป็นดัชนีฐานข้อมูลมาตรฐาน ดังที่สำรวจในงาน 'Ubiquitous B-tree' ของ Comer ในปี 1979 วิธีการเข้าถึงแบบแฮชและแผนการแฮชแบบไดนามิกได้พัฒนาขึ้นพร้อมกัน และทั้งสองตระกูลยังคงเป็นแกนหลักของทุกเอนจินเชิงสัมพันธ์

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

ทำไมจึงใช้ B+-trees แทนที่จะเป็น binary search trees ในฐานข้อมูล?

ฐานข้อมูลเก็บข้อมูลบนดิสก์ ซึ่งค่าใช้จ่ายส่วนใหญ่มาจากการอ่านหน้าข้อมูล B+-trees มี fanout สูง ดังนั้นแต่ละโหนดจะเติมเต็มหน้าดิสก์และโครงสร้างต้นไม้จะตื้นมาก ทำให้ต้องใช้ I/O เพียงไม่กี่ครั้งในการเข้าถึงเรคคอร์ดใดๆ Binary tree จะลึกกว่ามากและต้องมีการเข้าถึงดิสก์มากกว่า

เมื่อใดที่ควรใช้ดัชนีแฮชแทน B+-tree?

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