B + Tree là gì?
Một B + Tree chủ yếu được sử dụng để thực hiện đánh chỉ số năng độ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.
Trong hướng dẫn B + Tree này, bạn sẽ học:
- B + Tree là gì?
- Quy tắc cho B + Tree
- Tại sao sử dụng B + Tree
- Cây B + Cây so với Cây B
- Hoạt động tìm kiếm
- Chèn hoạt động
- Xóa hoạt động
Quy tắc cho B + Tree
Dưới đây là các quy tắc cần thiết cho B + Tree.
- Các 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 một giá trị khóa đích nhỏ hơn nút bên trong, thì điểm ngay phía bên trái của nó sẽ được theo sau.
- Nếu một giá trị khóa đích lớn hơn hoặc bằng nút bên trong, thì điểm ngay phía bên phải của nó sẽ được theo sau.
- Gốc có tối thiểu hai con.
Tại sao sử dụng B + Tree
Đây là lý do sử dụng B + Tree:
- Chìa 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 một "hệ số lấp đầy" để quản lý sự tăng và giảm của một cây.
- Trong cây B +, nhiều khóa có thể dễ dàng được đặt trên trang của 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 nằm trên nút lá.
- Việc quét toàn diện toàn bộ các phần tử là một cây chỉ cần một đường chuyề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 + Cây so với Cây B
Dưới đây là những điểm khác biệt chính giữa B + Tree và B Tree
| B + cây | B Cây |
| Các phím tìm kiếm có thể được lặp lại. | Các phím tìm kiếm không được thừa. |
| Dữ liệu chỉ được lưu trên các nút lá. | Cả nút lá và nút nội bộ đề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 và nhanh chóng hơn. | 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 một 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á. |
Hoạt động tìm kiếm
Trong B + Tree, tìm kiếm là một trong những thủ tục 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 có thể áp dụng:
- Để tìm bản ghi được yêu cầu, bạn cần thực hiện 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ả lại cho người dùng.
- Trong trường hợp khóa chính xác không được định vị bởi tìm kiếm trong 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" đượ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.
Thuật toán hoạt động tìm kiếm
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Đầu ra :
Bản ghi phù hợp được thiết lập với khóa chính xác được hiển thị cho người dùng; nếu không, một nỗ lực không thành công được hiển thị cho người dùng.
Chèn hoạt động
Thuật toán sau có thể áp dụng cho hoạt động chèn:
- 50 phần trăm các phần tử trong các nút được chuyển sang một lá mới để lưu trữ.
- Phần gốc 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 đầy đủ.
- Bây giờ, để 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 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 trong các bước trên.
Chèn thuật toán hoạt động
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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á 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 tạo thành 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ờ, 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 giá trị so với các nút khóa-giá trị ở bên phải.
Xóa hoạt động
Sự phức tạp của thủ tục xóa trong B + Tree vượt qua sự phức tạp của chức năng chèn và tìm kiếm.
Thuật toán sau có thể áp dụng khi xóa một phần tử khỏi B + Tree:
- Trước tiên, chúng ta cần xác định 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 các điều kiện chính xác của việc xóa bản ghi.
- Trường hợp nút lá chỉ đạt yếu tố thỏa mãn là đầy một nửa thì hoàn thành thao tác; nếu không, nút Lá có các mục nhập tối thiểu và không thể bị xóa.
- 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 nhập 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 nên 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 bên phải hoặc bên trái của nó, các mục nhập giá trị trong nút lá hoặc hàng xóm đượ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 thủ tục xóa một phần tử khỏi B + Tree của một thứ tự cụ thể.
- Đầu tiên, vị trí chính xác của phần tử sẽ bị xóa được xác định trong Cây.
- Ở đây phần tử sẽ bị 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, đó 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 các trường hợp của 31 trong Chỉ mục và Lá.
- Chúng ta có thể thấy rằng 31 có sẵn ở cả cấp độ nút Chỉ mục và nút 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 vào chỉ số 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ị nhỏ nhất và đặt nó làm chỉ mục. Vì vậy, 42 là giá trị duy nhất hiện tại, nó sẽ trở thành chỉ số.
Xóa thuật toán hoạt động
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Đầu ra :
Khóa "K" bị xóa và các khóa được mượn từ các anh chị em để điều chỉnh các giá trị trong n và các nút cha của nó nếu cần.
Tóm lược:
- B + Tree là một cấu trúc dữ liệu tự cân bằng để thực hiện các thủ tục tìm kiếm, chèn và xóa chính xác và nhanh hơn trên dữ liệu
- Chúng ta có thể dễ dàng truy xuất dữ liệu hoàn chỉnh hoặc dữ liệu từng phần vì đi qua cấu trúc cây được liên kết làm cho nó hoạt động hiệu quả.
- Cấu trúc cây B + phát triển và thu hẹp với 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à sự phân nhánh tiếp theo của các nút bên trong rõ ràng là rút ngắn chiều cao của cây, điều nà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 không gian hơn trên các thiết bị lưu trữ.