B+ TREE: Tìm kiếm, Chèn và Xóa Operations

Cây B+ là gì?

A Cây B+ Cây B+ chủ yếu được sử dụng để triển khai lập chỉ mục động ở nhiều cấp độ. So với cây B-Tree, cây B+ chỉ lưu trữ các con trỏ dữ liệu tại các nút lá của cây, giúp quá trình tìm kiếm chính xác và nhanh hơn.

Quy tắc cho cây B+

Dưới đây là những quy tắc thiết yếu cho một cây B+.

• Lá được sử dụng để lưu trữ các bản ghi dữ liệu.
• Các bản ghi được lưu trữ trong các nút bên trong của cây.
• Nếu giá trị khóa đích nhỏ hơn nút bên trong, thì con trỏ sẽ được theo dõi ngay bên trái nó.
• Nếu giá trị của khóa đích lớn hơn hoặc bằng nút bên trong, thì con trỏ nằm ngay bên phải nó sẽ được theo dõi.
• Gốc có tối thiểu hai con.

Tại sao nên sử dụng cây B+

Dưới đây là những lý do nên sử dụng cây B+:

• Các từ khóa chủ yếu được sử dụng để hỗ trợ tìm kiếm bằng cách chỉ dẫn đến trang phù hợp.
• Cây B+ sử dụng "hệ số lấp đầy" để quản lý sự tăng giảm của cây.
• Trong cây B+, nhiều khóa có thể dễ dàng được đặt trên trang bộ nhớ vì chúng không có dữ liệu liên quan đến các nút bên trong. Do đó, nó sẽ nhanh chóng truy cập dữ liệu cây trên nút lá.
• Việc quét toàn diện tất cả các phần tử chỉ cần một lần duyệt tuyến tính duy nhất vì tất cả các nút lá của cây B+ đều được liên kết với nhau.

Cây B+ so với cây B

Dưới đây là những điểm khác biệt chính giữa cây B+ và cây B.

Tìm kiếm Operasản xuất

Trong cây B+, tìm kiếm là một trong những thao tác dễ thực hiện nhất và cho kết quả nhanh chóng và chính xác.

Thuật toán tìm kiếm sau đây có thể áp dụng:

• Để tìm bản ghi cần thiết, bạn cần thực hiện lệnh Tìm kiếm nhị phân trên các bản ghi có sẵn trong Cây.
• Trong trường hợp khớp chính xác với khóa tìm kiếm, bản ghi tương ứng sẽ được trả về cho người dùng.
• Trong trường hợp khóa chính xác không được tìm thấy khi tìm kiếm ở nút cha, nút hiện tại hoặc nút lá, thì “thông báo không tìm thấy” sẽ được hiển thị cho người dùng.
• Quá trình tìm kiếm có thể được chạy lại để có kết quả tốt hơn và chính xác hơn.

Tìm kiếm Operathuật toán

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."

Đầu ra: Bộ bản ghi khớp với khóa chính xác sẽ được hiển thị cho người dùng; nếu không, người dùng sẽ được thông báo là nỗ lực không thành công.

Chèn Operasản xuất

Thuật toán sau đây có thể áp dụng cho thao tác chèn:

• 50 phần trăm phần tử trong các nút được chuyển sang một lá mới để lưu trữ.
• Nút cha của nút lá mới được liên kết chính xác với giá trị khóa tối thiểu và vị trí mới trong cây.
• Chia nút cha thành nhiều vị trí hơn trong trường hợp nó được sử dụng hết.
• Để có kết quả tốt hơn, khóa trung tâm được liên kết với nút cấp cao nhất của nút lá đó.
• Cho đến khi không tìm thấy nút cấp cao nhất, hãy tiếp tục lặp lại quy trình được giải thích ở các bước trên.

Chèn Operathuật toán

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.

Đầu ra: Thuật toán sẽ xác định phần tử và chèn thành công vào nút lá được yêu cầu.

Ví dụ mẫu B+ Tree ở trên được giải thích theo các bước bên dưới:

• Đầu tiên, chúng ta có 3 nút, và 3 phần tử đầu tiên, là 1, 4 và 6, được thêm vào các vị trí thích hợp trong các nút.
• Giá trị tiếp theo trong chuỗi dữ liệu là 12, cần được đưa vào Cây.
• Để thực hiện điều này, hãy chia nút và thêm 6 làm phần tử con trỏ.
• Bây giờ, một cấu trúc phân cấp bên phải của cây được tạo ra, và các giá trị dữ liệu còn lại được điều chỉnh tương ứng bằng cách giữ nguyên.ping Hãy ghi nhớ các quy tắc áp dụng cho giá trị bằng hoặc lớn hơn so với các cặp khóa-giá trị ở bên phải.

Xóa bỏ Operasản xuất

Độ phức tạp của quy trình xóa trong Cây B+ vượt xa chức năng chèn và tìm kiếm.

Thuật toán sau đây có thể áp dụng khi xóa một phần tử khỏi Cây B+:

• Đầu tiên, chúng ta cần xác định vị trí của một mục lá trong Cây chứa khóa và con trỏ, sau đó xóa mục lá đó khỏi Cây nếu mục lá đó đáp ứng chính xác các điều kiện xóa bản ghi.
• Nếu nút lá chỉ đáp ứng được yếu tố thỏa đáng là đầy một nửa, thì thao tác hoàn tất; ngược lại, nút lá có số lượng mục nhập tối thiểu và không thể bị xóa.
• Các nút liên kết khác ở bên phải và bên trái có thể xóa bất kỳ mục nào và sau đó di chuyển chúng đến nút lá. Nếu các tiêu chí này không được đáp ứng, thì chúng nên kết hợp nút lá và nút liên kết của nó trong cấu trúc cây phân cấp.
• Khi một nút lá được hợp nhất với các nút lân cận bên phải hoặc bên trái, các mục giá trị trong nút lá hoặc nút lân cận được liên kết trỏ đến nút cấp cao nhất sẽ bị xóa.

Ví dụ trên minh họa quy trình loại bỏ một phần tử khỏi cây B+ có thứ tự cụ thể.

• Đầu tiên, vị trí chính xác của phần tử cần xóa được xác định trong Cây.
• Ở đây, phần tử cần xóa chỉ có thể được xác định chính xác ở cấp độ lá chứ không phải ở vị trí chỉ mục. Do đó, phần tử có thể bị xóa mà không ảnh hưởng đến các quy tắc xóa, tức là giá trị của khóa tối thiểu.

• Trong ví dụ trên, chúng ta phải xóa 31 khỏi Cây.
• Chúng ta cần xác định vị trí các trường hợp xuất hiện của số 31 trong bảng Index và Leaf.
• Ta thấy rằng giá trị 31 có sẵn ở cả cấp độ nút Index và nút Leaf. Do đó, ta xóa nó khỏi cả hai trường hợp.
• Nhưng chúng ta phải điền chỉ mục trỏ đến 42. Bây giờ chúng ta sẽ xem xét đứa trẻ bên phải dưới 25 và lấy giá trị nhỏ nhất để đặt làm chỉ mục. Vì vậy, 42 là giá trị duy nhất hiện có, nó sẽ trở thành chỉ mục.

Xóa bỏ Operathuật toán

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

Đầu ra: Khóa “K” bị xóa và các khóa được mượn từ các khóa cùng cấp để điều chỉnh giá trị trong n và các nút cha của nó nếu cần.

Câu Hỏi Thường Gặp