B+ TREE : ค้นหา แทรก และลบ Operaตัวอย่าง

B+ Tree คืออะไร?

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

กฎสำหรับ B+ Tree

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

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

ทำไมต้องใช้ B+ Tree

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

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

B+ Tree กับ B Tree

นี่คือข้อแตกต่างหลักระหว่าง B+ Tree กับ B Tree

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

ค้นหา Operaการ

ใน B+ Tree การค้นหาเป็นหนึ่งในขั้นตอนที่ง่ายที่สุดในการดำเนินการและรับผลลัพธ์ที่รวดเร็วและแม่นยำ

สามารถใช้งานอัลกอริทึมการค้นหาได้ดังนี้:

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

ค้นหา Operaอัลกอริทึม

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

เอาท์พุต:

ระบบจะแสดงระเบียนที่ตรงกับคีย์ที่แน่นอนให้ผู้ใช้เห็น มิฉะนั้น ระบบจะแสดงความพยายามที่ล้มเหลวให้ผู้ใช้เห็น

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

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

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

สิ่งที่ใส่เข้าไป Operaอัลกอริทึม

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

เอาท์พุต:

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

ตัวอย่าง B+ Tree ข้างต้นอธิบายไว้ในขั้นตอนด้านล่าง:

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

ลบ Operaการ

ความซับซ้อนของขั้นตอนการลบใน B+ Tree จะเหนือกว่าฟังก์ชันการแทรกและค้นหา

อัลกอริทึมต่อไปนี้ใช้ได้ในการลบองค์ประกอบจาก B+ Tree:

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

ตัวอย่างข้างต้นแสดงขั้นตอนการลบองค์ประกอบออกจากแผนผัง B+ ของคำสั่งซื้อเฉพาะ

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

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

ลบ Operaอัลกอริทึม

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

เอาท์พุต:

คีย์ “K” จะถูกลบออก และคีย์จะถูกยืมมาจากพี่น้องเพื่อปรับค่าใน n และโหนดพาเรนต์ หากจำเป็น

สรุป

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