B TREE ในโครงสร้างข้อมูล: ค้นหา แทรก ลบ Operaตัวอย่าง

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

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

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

กฎสำหรับ B-Tree

นี่คือกฎสำคัญสำหรับการสร้าง B_Tree

  • ใบไม้ทั้งหมดจะถูกสร้างขึ้นในระดับเดียวกัน
  • B-Tree ถูกกำหนดโดยระดับหนึ่ง ซึ่งเรียกอีกอย่างว่า “ลำดับ” (ระบุโดยนักแสดงภายนอก เช่น โปรแกรมเมอร์) เรียกว่า
    m

    เป็นต้นไป คุณค่าของ

    m

    ขึ้นอยู่กับขนาดบล็อกบนดิสก์ซึ่งข้อมูลอยู่เป็นหลัก

  • แผนผังย่อยด้านซ้ายของโหนดจะมีค่าน้อยกว่าด้านขวาของแผนผังย่อย ซึ่งหมายความว่าโหนดจะถูกจัดเรียงจากน้อยไปมากจากซ้ายไปขวา
  • จำนวนสูงสุดของโหนดย่อย โหนดรูท รวมถึงโหนดย่อยสามารถมีได้คำนวณโดยสูตรนี้:
    m – 1

    ตัวอย่างเช่น:

    m = 4
    max keys: 4 – 1 = 3
    

กฎสำหรับ B-Tree

  • ทุกโหนด ยกเว้นรูท จะต้องมีคีย์ขั้นต่ำของ
    [m/2]-1

    ตัวอย่างเช่น:

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

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

นี่คือเหตุผลในการใช้ B-Tree

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

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

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

ค้นหา Operaการ

การดำเนินการค้นหาเป็นการดำเนินการที่ง่ายที่สุดบน B Tree

มีการใช้อัลกอริทึมดังต่อไปนี้:

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

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

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

ใช้อัลกอริทึมต่อไปนี้:

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

เนื่องจากโหนดเต็ม ดังนั้นโหนดจะแยก จากนั้นจึงแทรกค่าใหม่

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ลบ Operaการ

การดำเนินการลบมีกฎมากกว่าการแทรกและการค้นหา

ใช้อัลกอริทึมต่อไปนี้:

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

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

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

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

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

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

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

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

ลบ Operaการ

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

ลบ Operaการ

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

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

ลบ Operaการ

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

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

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

ลบ Operaการ

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

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

ลบ Operaการ

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

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

ดูขั้นตอนการลบคีย์ดังกล่าว:

ลบ Operaการ

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

ลบ Operaรหัสหลอก

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
    }
}

เอาท์พุต:

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

สรุป

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