แบบสอบถาม B-tree ในโครงสร้างข้อมูล

ที่นี่เราจะดูวิธีการค้นหาใน B-Tree การค้นหา B-Tree เรียกอีกอย่างว่าการค้นหา B-Tree สมมติว่าเรามี B-tree ด้านล่าง −

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

เทคนิคการค้นหาคล้ายกับแผนผังการค้นหาแบบไบนารีมาก สมมติว่าเราต้องการค้นหา 66 จากต้นไม้ด้านบน ดังนั้นเราจะเริ่มจากรูท ตอนนี้ 66 ใหญ่กว่าองค์ประกอบรูท 46 ดังนั้นเราจะย้ายไปที่ลูกที่ถูกต้องของรูท จากนั้นลูกที่ถูกต้องจะมีองค์ประกอบมากกว่าหนึ่งรายการ มีการจัดเรียงองค์ประกอบคือ [56, 81] คีย์เป้าหมายของเรามีขนาดใหญ่กว่า 56 แต่เล็กกว่า 81 ดังนั้นเราจะเข้าสู่แผนผังย่อยซึ่งอยู่ระหว่าง 56 ถึง 81 ดังนั้นเราได้ย้ายไปยังระดับลีฟ เมื่อถึงจุดนั้นเราได้ธาตุ 66

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

อัลกอริทึม

BTreeSearch(รูท, คีย์) −

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

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

x := Read root
if x is an index node, then
   if there is an object o in x, such that o->key = ‘key’, then return o->val
   Find the child of x, as x->child[i], whose key range is containing ‘key’
   return BTreeSearch(x->child[i], key)
else
   if there is an object o in x, such that o->key = ‘key’, then return o->val,
   else return null
   end if
end if