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
- ทุกโหนด ยกเว้นรูท จะต้องมีคีย์ขั้นต่ำของ
[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 | สิ่งต่อไปนี้ไม่เป็นความจริงเกี่ยวกับอัลกอริทึมการแทรก:
เนื่องจากโหนดเต็ม ดังนั้นโหนดจะแยก จากนั้นจึงแทรกค่าใหม่ |
ในตัวอย่างข้างต้น:
- ค้นหาตำแหน่งที่เหมาะสมในโหนดสำหรับคีย์
- ใส่คีย์ในโหนดเป้าหมาย และตรวจสอบกฎ
- หลังจากการแทรก โหนดมีจำนวนคีย์มากกว่าจำนวนขั้นต่ำซึ่งก็คือ 1 หรือไม่ ในกรณีนี้ใช่แล้ว ตรวจสอบกฎถัดไป
- หลังจากการแทรก โหนดมีจำนวนคีย์มากกว่าจำนวนสูงสุด ซึ่งก็คือ 3 หรือไม่ ในกรณีนี้ ไม่ มันไม่ได้เป็นเช่นนั้น ซึ่งหมายความว่า B Tree ไม่ได้ละเมิดกฎใดๆ และการแทรกเสร็จสมบูรณ์
ในตัวอย่างข้างต้น:
- โหนดมีจำนวนคีย์ถึงจำนวนสูงสุดแล้ว
- โหนดจะแยกออก และคีย์กลางจะกลายเป็นโหนดรูทของอีก 2 โหนดที่เหลือ
- ในกรณีที่มีคีย์เป็นเลขคู่ โหนดกลางจะถูกเลือกโดยอคติซ้ายหรืออคติขวา
ในตัวอย่างข้างต้น:
- โหนดมีคีย์น้อยกว่าค่าสูงสุด
- 1 ถูกแทรกถัดจาก 3 แต่กฎการเรียงลำดับจากน้อยไปมากถูกละเมิด
- เพื่อแก้ไขปัญหานี้ จะมีการจัดเรียงคีย์ต่างๆ
ในทำนองเดียวกัน สามารถแทรก 13 และ 2 ลงในโหนดได้อย่างง่ายดาย เนื่องจากเป็นไปตามกฎคีย์สูงสุดที่น้อยกว่าสำหรับโหนด
ในตัวอย่างข้างต้น:
- โหนดมีคีย์เท่ากับคีย์สูงสุด
- คีย์ถูกแทรกลงในโหนดเป้าหมาย แต่ละเมิดกฎของคีย์สูงสุด
- โหนดเป้าหมายถูกแยกออก และคีย์กลางโดยอคติซ้ายกลายเป็นพาเรนต์ของโหนดย่อยใหม่
- โหนดใหม่จะจัดเรียงตามลำดับจากน้อยไปหามาก
ในทำนองเดียวกัน ตามกฎและกรณีข้างต้น ค่าที่เหลือสามารถแทรกลงใน B Tree ได้อย่างง่ายดาย
ลบ Operaการ
การดำเนินการลบมีกฎมากกว่าการแทรกและการค้นหา
ใช้อัลกอริทึมต่อไปนี้:
- ดำเนินการค้นหาและค้นหาคีย์เป้าหมายในโหนด
- มีเงื่อนไขสามประการที่ใช้ขึ้นอยู่กับตำแหน่งของคีย์เป้าหมาย ดังที่อธิบายไว้ในหัวข้อต่อไปนี้
หากคีย์เป้าหมายอยู่ในโหนดปลายสุด
- Target อยู่ในโหนดปลายสุด มากกว่าคีย์ขั้นต่ำ
- การลบสิ่งนี้จะไม่เป็นการละเมิดทรัพย์สินของ B Tree
- Target อยู่ในลีฟโหนด แต่ก็มีโหนดคีย์ขั้นต่ำ
- การลบสิ่งนี้จะเป็นการละเมิดทรัพย์สินของ B Tree
- Target โหนดสามารถยืมคีย์จากโหนดซ้ายทันทีหรือโหนดขวาทันที (พี่น้อง)
- น้องจะบอกว่า ใช่ หากมีจำนวนคีย์มากกว่าขั้นต่ำ
- คีย์จะถูกยืมจากโหนดหลัก ค่าสูงสุดจะถูกโอนไปยังโหนดหลัก ค่าสูงสุดของโหนดหลักจะถูกโอนไปยังโหนดเป้าหมาย และลบค่าเป้าหมายออก
- Target อยู่ในโหนดปลายสุด แต่ไม่มีพี่น้องคนใดที่มีคีย์มากกว่าจำนวนขั้นต่ำ
- ค้นหาคีย์
- ผสานกับพี่น้องและโหนดพาเรนต์ขั้นต่ำ
- จำนวนคีย์ทั้งหมดจะมากกว่าค่าต่ำสุด
- คีย์เป้าหมายจะถูกแทนที่ด้วยโหนดหลักขั้นต่ำ
หากคีย์เป้าหมายอยู่ในโหนดภายใน
- เลือกแบบลำดับก่อนหรือแบบสืบทอดตามลำดับ
- ในกรณีที่เป็นลำดับก่อนหน้า คีย์สูงสุดจากแผนผังย่อยด้านซ้ายจะถูกเลือก
- ในกรณีที่เป็นผู้สืบทอดตามลำดับ คีย์ขั้นต่ำจากแผนผังย่อยด้านขวาจะถูกเลือก
- หากคีย์เป้าหมายมีลำดับก่อนหน้ามากกว่าคีย์ min ก็จะสามารถแทนที่คีย์เป้าหมายด้วยค่าสูงสุดของคีย์ก่อนหน้าตามลำดับ
- หากคีย์ก่อนหน้าของคีย์เป้าหมายไม่มีคีย์มากกว่า min ให้มองหาคีย์ขั้นต่ำของคีย์เป้าหมายที่ตามลำดับ
- หากคีย์เป้าหมายตามลำดับและคีย์เป้าหมายมีน้อยกว่าคีย์ขั้นต่ำ ให้รวมคีย์ก่อนหน้าและคีย์สืบทอด
หากคีย์เป้าหมายอยู่ในโหนดรูท
- แทนที่ด้วยองค์ประกอบสูงสุดของทรีย่อยก่อนหน้าตามลำดับ
- หลังจากลบแล้ว หากเป้าหมายมีคีย์ขั้นต่ำน้อยกว่า โหนดเป้าหมายจะยืมค่าสูงสุดจากพี่น้องผ่านทางผู้ปกครองของพี่น้อง
- ค่าสูงสุดของพาเรนต์จะถูกยึดโดยเป้าหมาย แต่จะมีโหนดที่มีค่าสูงสุดของพี่น้อง
ตอนนี้มาทำความเข้าใจการดำเนินการลบพร้อมตัวอย่างกัน
ไดอะแกรมด้านบนแสดงกรณีต่างๆ ของการดำเนินการลบใน B-Tree B-Tree นี้มีลำดับที่ 5 ซึ่งหมายความว่าจำนวนโหนดย่อยขั้นต่ำที่โหนดใดๆ สามารถมีได้คือ 3 และจำนวนโหนดย่อยสูงสุดที่โหนดใดๆ สามารถมีได้คือ 5 ในขณะที่จำนวนคีย์ขั้นต่ำและสูงสุดที่โหนดใดๆ สามารถมีได้คือ 2 และ 4 ตามลำดับ
ในตัวอย่างข้างต้น:
- โหนดเป้าหมายมีคีย์เป้าหมายที่จะลบ
- โหนดเป้าหมายมีคีย์มากกว่าคีย์ขั้นต่ำ
- เพียงลบกุญแจ
ในตัวอย่างข้างต้น:
- โหนดเป้าหมายมีคีย์เท่ากับคีย์ขั้นต่ำ ดังนั้นจึงไม่สามารถลบออกโดยตรงได้เนื่องจากจะละเมิดเงื่อนไข
แผนภาพต่อไปนี้จะอธิบายวิธีการลบคีย์นี้:
- โหนดเป้าหมายจะยืมคีย์จากพี่น้องโดยตรง ในกรณีนี้ ตามลำดับก่อนหน้า (พี่น้องด้านซ้าย) เนื่องจากไม่มีผู้สืบทอดตามลำดับ (พี่น้องด้านขวา)
- ค่าสูงสุดของลำดับก่อนหน้าจะถูกโอนไปยังพาเรนต์ และพาเรนต์จะโอนค่าสูงสุดไปยังโหนดเป้าหมาย (ดูแผนภาพด้านล่าง)
ตัวอย่างต่อไปนี้แสดงให้เห็นวิธีการลบคีย์ที่ต้องการค่าจากตัวสืบทอดตามลำดับ
- โหนดเป้าหมายจะยืมคีย์จากพี่น้องโดยตรง ในกรณีนี้ ตามลำดับที่สืบทอด (พี่น้องทางขวา) เนื่องจากเป็นลำดับก่อนหน้า (พี่น้องทางซ้าย) มีคีย์เท่ากับคีย์ขั้นต่ำ
- ค่าต่ำสุดของผู้สืบทอดตามลำดับจะถูกโอนไปยังพาเรนต์ และพาเรนต์จะโอนค่าสูงสุดไปยังโหนดเป้าหมาย
ในตัวอย่างด้านล่าง โหนดเป้าหมายไม่มีพี่น้องใด ๆ ที่สามารถมอบคีย์ให้กับโหนดเป้าหมายได้ ดังนั้นจึงจำเป็นต้องมีการผสานกัน
ดูขั้นตอนการลบคีย์ดังกล่าว:
- รวมโหนดเป้าหมายกับพี่น้องที่อยู่ติดกันพร้อมกับคีย์หลัก
- คีย์จากโหนดหลักถูกเลือกให้พี่น้องอยู่ระหว่างโหนดที่รวมเข้าด้วยกัน
- ลบคีย์เป้าหมายออกจากโหนดที่ผสาน
ลบ 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 ก่อนอื่นจะค้นหาคีย์เป้าหมายที่ต้องการลบ จากนั้นจึงลบคีย์นั้น แล้วประเมินความถูกต้องโดยพิจารณาจากกรณีต่างๆ เช่น คีย์ต่ำสุดและสูงสุดของโหนดเป้าหมาย โหนดที่เกี่ยวข้อง และโหนดเหนือ