แบบสอบถามต้นไม้ B+ ในโครงสร้างข้อมูล

ที่นี่เราจะดูวิธีดำเนินการค้นหาใน B+ Tree การค้นหา B+ Tree เรียกอีกอย่างว่า B+ Tree Querying อัลกอริธึมนี้คล้ายกับการสืบค้นของ B-Tree อย่างมาก นอกจากนี้ยังรองรับการสืบค้นข้อมูลตามช่วง สมมติว่าเรามีต้นไม้ B+ ด้านล่าง −

ตัวอย่าง B+ Tree −

เทคนิคการค้นหาคล้ายกับแผนผังการค้นหาแบบไบนารีมาก สมมติว่าเราต้องการค้นหา 63 จากต้นไม้ด้านบน ดังนั้นเราจะเริ่มจากรูท ตอนนี้ 63 ใหญ่กว่าองค์ประกอบรูท 60 แต่เล็กกว่า 75 ดังนั้นเราจะย้ายไปยังลูกที่ถูกต้องขององค์ประกอบ 60 ลูกที่ถูกต้องคือ 63 แต่ถ้าเราใช้ B Tree นั่นจะเป็น ผลลัพธ์. ในกรณีนี้เนื่องจากโหนดปัจจุบันเป็นโหนดภายใน ดังนั้นนั่นจึงไม่ใช่ข้อมูลจริง เราต้องย้ายไปที่ลูกที่ถูกต้องก่อน และที่ระดับใบไม้ เราสามารถหา 63 เป็นบันทึกได้ นั่นจะเป็นผลลัพธ์ที่แท้จริง

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

ให้เราดูอัลกอริธึมเพื่อค้นหาองค์ประกอบภายใน B-Tree

อัลกอริทึม

BPlusTreeSearch(รูท, คีย์) -

อินพุต − รากของต้นไม้และกุญแจสำคัญในการค้นหา

ผลลัพธ์ − ค่าของโหนดที่มีคีย์ หากไม่มีอยู่ ให้คืนค่า null

Apply binary search on records
if record with the ‘key’ is found, then
   return required record
else if current node is leaf node, and key is not found, then
   return null