B+ TREE: ค้นหา แทรก และลบ Operations

B+ Tree คืออะไร?

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

กฎสำหรับ B+ Tree

นี่คือกฎสำคัญสำหรับต้นไม้ระดับ B+

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

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

ต่อไปนี้คือเหตุผลที่ควรใช้ B+ Tree:

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

B+ Tree กับ B Tree

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

ค้นหา 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."

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

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

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

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

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

1. If 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.

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

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

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

ลบ Operaการ

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

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

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

ตัวอย่างข้างต้นแสดงขั้นตอนการลบองค์ประกอบออกจาก B+ Tree ของลำดับที่กำหนด

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

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

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

1) Start at the root and go up to the 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

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

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