โครงสร้างข้อมูลแบบ B Tree: การค้นหา การแทรก การลบ

บีทรีคืออะไร?

บี ทรี B Tree คือโครงสร้างข้อมูลที่ปรับสมดุลได้ด้วยตนเอง โดยอาศัยชุดกฎเฉพาะสำหรับการค้นหา แทรก และลบข้อมูลในลักษณะที่รวดเร็วและประหยัดหน่วยความจำ เพื่อให้บรรลุเป้าหมายนี้ จึงต้องปฏิบัติตามกฎต่อไปนี้ในการสร้าง B Tree

B-Tree เป็นโครงสร้างข้อมูลประเภทต้นไม้แบบพิเศษ วิธีการนี้ได้รับการแนะนำครั้งแรกในปี 1972 โดย McCreight และ Bayer ซึ่งตั้งชื่อว่า Height Balanced m-way Search Tree B-Tree ช่วยให้รักษาการเรียงลำดับของข้อมูลและช่วยให้สามารถดำเนินการต่างๆ เช่น การแทรก การค้นหา และการลบได้ในเวลาที่น้อยลง

กฎสำหรับ B-Tree

ต่อไปนี้เป็นกฎสำคัญสำหรับการสร้าง B-Tree:

• ใบไม้ทั้งหมดจะถูกสร้างขึ้นในระดับเดียวกัน
• โครงสร้าง B-Tree ถูกกำหนดโดยจำนวนดีกรี ซึ่งเรียกอีกอย่างว่า "ลำดับ" (กำหนดโดยผู้กระทำภายนอก เช่น โปรแกรมเมอร์) ซึ่งเรียกว่า m เป็นต้นไป คุณค่าของ m ขึ้นอยู่กับขนาดบล็อกบนดิสก์ซึ่งข้อมูลอยู่เป็นหลัก
• แผนผังย่อยด้านซ้ายของโหนดจะมีค่าน้อยกว่าด้านขวาของแผนผังย่อย ซึ่งหมายความว่าโหนดจะถูกจัดเรียงจากน้อยไปมากจากซ้ายไปขวา
• จำนวนคีย์สูงสุดที่โหนดรากและโหนดลูกสามารถมีได้นั้น คำนวณได้จากสูตรนี้: m − 1. ตัวอย่างเช่น:

  m = 4
  max keys: 4 − 1 = 3

• ทุกโหนด ยกเว้นโหนดราก ต้องมีจำนวนคีย์ขั้นต่ำดังนี้ [m/2] − 1. ตัวอย่างเช่น:

  m = 4
  min keys: 4/2 − 1 = 1

• จำนวนสูงสุดของโหนดย่อยที่โหนดสามารถมีได้เท่ากับระดับของมัน ซึ่งก็คือ m.
• ลูกขั้นต่ำที่โหนดสามารถมีได้คือครึ่งหนึ่งของลำดับ ซึ่งก็คือ m/2 (ใช้ค่าเพดาน)
• คีย์ทั้งหมดในโหนดจะถูกจัดเรียงตามลำดับที่เพิ่มขึ้น

ทำไมต้องใช้บีทรี

ต่อไปนี้คือเหตุผลในการใช้โครงสร้างข้อมูลแบบ B-Tree:

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

ประวัติของบีทรี

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

ค้นหา Operaการ

การค้นหาเป็นการดำเนินการที่ง่ายที่สุดบน B Tree โดยใช้อัลกอริธึมต่อไปนี้:

• ให้คีย์ (ค่า) ที่ต้องการค้นหาคือ “k”
• เริ่มการค้นหาจากรากและย้อนกลับลงมาอย่างต่อเนื่อง
• ถ้า k น้อยกว่าค่าราก ให้ค้นหาในซับทรีด้านซ้าย ถ้า k มากกว่าค่าราก ให้ค้นหาในซับทรีด้านขวา
• หากโหนดมี k ที่พบ เพียงแค่ส่งคืนโหนด
• หากไม่พบ k ในโหนด ให้ข้ามไปยังรายการย่อยด้วยคีย์ที่มากกว่า
• หากไม่พบ k ในแผนผัง เราจะคืนค่า NULL

สิ่งที่ใส่เข้าไป Operaการ

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

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

ในตัวอย่างข้างต้น:

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

ในตัวอย่างข้างต้น:

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

ในตัวอย่างข้างต้น:

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

ในทำนองเดียวกัน สามารถแทรกเลข 13 และ 2 ลงในโหนดได้อย่างง่ายดาย เนื่องจากตรงตามกฎ "จำนวนคีย์น้อยกว่าจำนวนคีย์สูงสุด" สำหรับโหนดเหล่านั้น

ในตัวอย่างข้างต้น:

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

ในทำนองเดียวกัน ตามกฎและกรณีข้างต้น ค่าที่เหลือสามารถแทรกลงใน B Tree ได้อย่างง่ายดาย

ลบ Operaการ

การลบข้อมูลมีกฎเกณฑ์มากกว่าการแทรกและการค้นหาข้อมูล โดยใช้อัลกอริทึมดังต่อไปนี้:

• ดำเนินการค้นหาและค้นหาคีย์เป้าหมายในโหนดต่างๆ
• มีการนำเงื่อนไขสามข้อมาใช้โดยพิจารณาจากตำแหน่งของคีย์เป้าหมาย ดังที่อธิบายไว้ในหัวข้อต่อไปนี้

หากคีย์เป้าหมายอยู่ในโหนดปลายสุด

• Target อยู่ในโหนดใบ มากกว่าค่า min keys การลบข้อมูลนี้จะไม่ละเมิดคุณสมบัติของ B Tree
• Target อยู่ในโหนดใบ และมีโหนดคีย์ขั้นต่ำ การลบโหนดนี้จะละเมิดคุณสมบัติของ B Tree
• โหนดเป้าหมายสามารถยืมคีย์จากโหนดซ้ายสุดหรือโหนดขวาสุด (โหนดพี่น้อง) ได้
• น้องจะบอกว่า ใช่ ถ้ามีจำนวนคีย์มากกว่าจำนวนขั้นต่ำ
• คีย์จะถูกยืมมาจากโหนดแม่ ค่าสูงสุดจะถูกส่งต่อไปยังโหนดแม่ ค่าสูงสุดของโหนดแม่จะถูกส่งต่อไปยังโหนดเป้าหมาย และค่าในโหนดเป้าหมายจะถูกลบออก
• Target หากอยู่ในโหนดใบ แต่ไม่มีโหนดพี่น้องใดที่มีคีย์มากกว่าจำนวนขั้นต่ำ ให้ค้นหาคีย์นั้น ผสานรวมกับโหนดพี่น้องและโหนดแม่ที่มีจำนวนคีย์น้อยที่สุด จำนวนคีย์ทั้งหมดจะมากกว่าจำนวนขั้นต่ำ และคีย์เป้าหมายจะถูกแทนที่ด้วยจำนวนคีย์น้อยที่สุดของโหนดแม่

หากคีย์เป้าหมายอยู่ในโหนดภายใน

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

หากคีย์เป้าหมายอยู่ในโหนดรูท

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

ตอนนี้มาทำความเข้าใจการดำเนินการลบพร้อมตัวอย่างกัน

แผนภาพด้านบนแสดงกรณีต่างๆ ของการดำเนินการลบใน B-Tree B-Tree นี้มีลำดับที่ 5 ซึ่งหมายความว่าจำนวนโหนดลูกขั้นต่ำที่โหนดใดๆ สามารถมีได้คือ 3 และจำนวนโหนดลูกสูงสุดที่โหนดใดๆ สามารถมีได้คือ 5 ในขณะที่จำนวนคีย์ขั้นต่ำและสูงสุดที่โหนดใดๆ สามารถมีได้คือ 2 และ 4 ตามลำดับ

ในตัวอย่างข้างต้น:

• โหนดเป้าหมายมีคีย์เป้าหมายที่จะลบ
• โหนดเป้าหมายมีจำนวนคีย์มากกว่าจำนวนคีย์ขั้นต่ำ
• ลบคีย์นั้นทิ้งไปได้เลย

ในตัวอย่างข้างต้น:

• โหนดเป้าหมายมีคีย์เท่ากับจำนวนคีย์ขั้นต่ำ ดังนั้นเราจึงไม่สามารถลบโหนดนั้นโดยตรงได้ เนื่องจากจะขัดกับเงื่อนไข

แผนภาพต่อไปนี้จะอธิบายวิธีการลบคีย์นี้:

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

ตัวอย่างต่อไปนี้แสดงให้เห็นวิธีการลบคีย์ที่ต้องการค่าจากตัวสืบทอดตามลำดับ

• โหนดเป้าหมายจะยืมคีย์จากโหนดพี่น้องที่อยู่ติดกัน ในกรณีนี้คือโหนดผู้สืบทอดตามลำดับ (โหนดพี่น้องทางขวา) เนื่องจากโหนดผู้มาก่อนตามลำดับ (โหนดพี่น้องทางซ้าย) มีคีย์เท่ากับคีย์ขั้นต่ำ
• ค่าต่ำสุดของผู้สืบทอดตามลำดับจะถูกโอนไปยังพาเรนต์ และพาเรนต์จะโอนค่าสูงสุดไปยังโหนดเป้าหมาย

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

• รวมโหนดเป้าหมายเข้ากับโหนดพี่น้องโดยตรงใดๆ ก็ได้ พร้อมด้วยคีย์หลัก
• จะเลือกคีย์จากโหนดหลักที่อยู่ระหว่างโหนดที่รวมกันทั้งสองโหนด
• ลบคีย์เป้าหมายออกจากโหนดที่รวมกันแล้ว

ลบ Operation Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Output: องค์ประกอบที่ใหญ่ที่สุดจะถูกลบออกจาก B-Tree

คำถามที่พบบ่อย