B+ TREE : Tìm kiếm, chèn và xóa Operaví dụ

Cây B+ là gì?

A Cây B+ chủ yếu được sử dụng để thực hiện lập chỉ mục động trên nhiều cấp độ. So với B- Tree, B+ Tree 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 hơn và nhanh hơn.

Quy tắc cho cây B+

Dưới đây là những quy tắc cần thiết cho B+ Tree.

• Lá được sử dụng để lưu trữ các bản ghi dữ liệu.
• Nó được lưu trữ trong các nút bên trong của Cây.
• Nếu giá trị khóa mục tiêu nhỏ hơn nút bên trong thì điểm ngay bên trái của nó sẽ được theo sau.
• Nếu giá trị khóa mục tiêu lớn hơn hoặc bằng nút bên trong thì điểm ngay bên phải của nút đó sẽ được theo sau.
• 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 B+ Tree:

• Khóa chủ yếu được sử dụng để hỗ trợ tìm kiếm bằng cách hướng đến Lá thích hợp.
• B+ Tree sử dụng “hệ số lấp đầy” để quản lý việc tăng và giảm trong 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á.
• Quét toàn bộ toàn bộ tất cả các phần tử là một cây chỉ cần một đường truyền tuyến tính 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

Cây B+	Cây B
Phím tìm kiếm có thể được lặp lại.	Phím tìm kiếm không thể dư thừa.
Dữ liệu chỉ được lưu trên các nút lá.	Cả nút lá và nút bên trong đều có thể lưu trữ dữ liệu
Dữ liệu được lưu trữ trên nút lá giúp việc tìm kiếm chính xác hơn và nhanh hơn.	Việc tìm kiếm chậm do dữ liệu được lưu trữ trên Leaf và các nút bên trong.
Việc xóa không khó vì một phần tử chỉ bị xóa khỏi nút lá.	Xóa các phần tử là một quá trình phức tạp và tốn thời gian.
Các nút lá được liên kết giúp tìm kiếm hiệu quả và nhanh chóng.	Bạn không thể liên kết các nút lá.

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

Trong B+ Tree, tìm kiếm là một trong những quy trình dễ thực hiện nhất và nhận được kết quả nhanh chóng và chính xác từ nó.

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ữ.
• Cha mẹ của 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.
• Bây giờ, để có kết quả tốt hơn, phím trung tâm được liên kết với nút cấp cao nhất của 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.	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.  

Đầ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 coi là một phần của Cây.
• Để đạt được điều này, hãy chia nút, thêm 6 làm phần tử con trỏ.
• Bây giờ, hệ thống phân cấp bên phải của cây đã được tạo và các giá trị dữ liệu còn lại được điều chỉnh tương ứng bằng cách ghi nhớ các quy tắc áp dụng bằng hoặc lớn hơn các giá trị đối với các nút 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í một mục lá trong Cây đang giữ khóa và con trỏ. , xóa mục nhập lá khỏi Cây nếu Lá đáp ứng chính xác các điều kiện xóa bản ghi.
• Trong trường hợp nút lá chỉ đáp ứng yếu tố thỏa đáng là đầy một nửa thì thao tác được hoàn thành; nếu không, nút lá có số mục nhập tối thiểu và không thể xóa được.
• Các nút được liên kết khác ở bên phải và bên trái có thể bỏ trống bất kỳ mục nào sau đó di chuyển chúng đến Lá. Nếu các tiêu chí này không được đáp ứng thì chúng sẽ kết hợp nút lá và nút liên kết của nó trong hệ thống phân cấp cây.
• Khi hợp nhất nút lá với các nút lân cận ở bên phải hoặc bên trái, các mục nhập 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+ theo một 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 quy tắc xóa, đó 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 phiên bản 31 trong Index và Leaf.
• Chúng ta có thể thấy rằng 31 có sẵn ở cả cấp độ nút Chỉ mục và Lá. Do đó, chúng tôi xóa nó khỏi cả hai trường hợp.
• Tuy nhiên, chúng ta phải điền chỉ mục trỏ đến 42. Bây giờ chúng ta sẽ xem xét đúng đứa trẻ dưới 25 tuổi và lấy giá trị tối thiểu và đặt nó làm chỉ mục. Vì vậy, 42 là giá trị duy nhất hiện diện, nó sẽ trở thành chỉ mục.

Xóa bỏ Operathuật toán

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

Đầu ra:

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

Tổng kết

• B+ Tree là cây tự cân bằng cấu trúc dữ liệu để thực hiện tìm kiếm, chèn và xóa dữ liệu chính xác và nhanh hơn
• Chúng ta có thể dễ dàng truy xuất dữ liệu đầy đủ hoặc một phần dữ liệu vì việc đi qua cấu trúc cây liên kết sẽ làm cho nó hiệu quả.
• Cấu trúc cây B+ phát triển và thu nhỏ theo sự tăng/giảm số lượng bản ghi được lưu trữ.
• Việc lưu trữ dữ liệu trên các nút lá và phân nhánh tiếp theo của các nút bên trong rõ ràng sẽ rút ngắn chiều cao của cây, làm giảm các hoạt động đầu vào và đầu ra của đĩa, cuối cùng tiêu tốn ít dung lượng hơn trên các thiết bị lưu trữ.