Cây B là gì?
B Tree là một cấu trúc dữ liệu tự cân bằng dựa trên một bộ quy tắc cụ thể để tìm kiếm, chèn và xóa dữ liệu một cách nhanh hơn và hiệu quả về bộ nhớ. Để đạt được điều này, các quy tắc sau đây được tuân theo để tạo B Tree.
Cây B là một loại cây đặc biệt trong cấu trúc dữ liệu. Năm 1972, phương pháp này lần đầu tiên được giới thiệu bởi McCreight, và Bayer đặt tên cho nó là Cây tìm kiếm m chiều cân bằng chiều cao. Nó giúp bạn lưu giữ dữ liệu được sắp xếp và cho phép các hoạt động khác nhau như Chèn, tìm kiếm và xóa trong thời gian ngắn hơn.
Trong hướng dẫn B-Tree này, bạn sẽ học:
- Cây B là gì?
- Tại sao sử dụng B-Tree
- Lịch sử của B Tree
- Hoạt động tìm kiếm
- Chèn hoạt động
- Xóa hoạt động
Quy tắc cho B-Tree
Đây là các quy tắc quan trọng để tạo B_Tree
- Tất cả các lá sẽ được tạo ở cùng một cấp độ.
- B-Tree được xác định bởi một số mức độ, còn được gọi là "thứ tự" (được chỉ định bởi một tác nhân bên ngoài, như một lập trình viên), được gọi là
m
trở đi. Giá trị củam
phụ thuộc vào kích thước khối trên đĩa chứa dữ liệu chủ yếu. - Cây con bên trái của nút sẽ có giá trị nhỏ hơn bên phải của cây con. Điều này có nghĩa là các nút cũng được sắp xếp theo thứ tự tăng dần từ trái sang phải.
- Số lượng tối đa các nút con, một nút gốc cũng như các nút con của nó có thể chứa được tính theo công thức sau:
m - 1
Ví dụ:m = 4max keys: 4 - 1 = 3
- Mọi nút, ngoại trừ gốc, phải chứa các khóa tối thiểu là
[m/2]-1
Ví dụ:m = 4min keys: 4/2-1 = 1
- Số lượng nút con tối đa mà một nút có thể có bằng với mức độ của nó, là
m
- Số nút con tối thiểu mà một nút có thể có là một nửa đơn hàng, là m / 2 (lấy giá trị trần).
- Tất cả các khóa trong một nút được sắp xếp theo thứ tự tăng dần.
Tại sao sử dụng B-Tree
Đây là lý do sử dụng B-Tree
- Giảm số lần đọc trên đĩa
- B Cây có thể được tối ưu hóa dễ dàng để điều chỉnh kích thước của nó (đó là số lượng nút con) theo kích thước đĩa
- Đây là một kỹ thuật được thiết kế đặc biệt để xử lý một lượng lớn dữ liệu.
- Nó là một thuật toán hữu ích cho cơ sở dữ liệu và hệ thống tệp.
- Một lựa chọn tốt để chọn khi đọc và ghi các khối dữ liệu lớn
Lịch sử của B Tree
- Dữ liệu được lưu trên đĩa thành từng khối, dữ liệu này khi được đưa vào bộ nhớ chính (hay RAM) được gọi là cấu trúc dữ liệu.
- Trong trường hợp dữ liệu lớn, việc tìm kiếm một bản ghi trong đĩa yêu cầu đọc toàn bộ đĩa; điều này làm tăng thời gian và mức tiêu thụ bộ nhớ chính do tần suất truy cập đĩa và kích thước dữ liệu cao.
- Để khắc phục điều này, các bảng chỉ mục được tạo ra để lưu tham chiếu bản ghi của các bản ghi dựa trên các khối mà chúng nằm trong đó. Điều này làm giảm đáng kể thời gian và mức tiêu thụ bộ nhớ.
- Vì chúng tôi có dữ liệu khổng lồ, chúng tôi có thể tạo các bảng chỉ mục nhiều cấp.
- Chỉ mục đa cấp có thể được thiết kế bằng cách sử dụng B Tree để giữ cho dữ liệu được sắp xếp theo kiểu tự cân bằng.
Hoạt động tìm kiếm
Thao tác tìm kiếm là thao tác đơn giản nhất trên B Tree.
Thuật toán sau được áp dụng:
- Cho khóa (giá trị) được tìm kiếm bởi "k".
- Bắt đầu tìm kiếm từ gốc và duyệt xuống một cách đệ quy.
- Nếu k nhỏ hơn giá trị gốc, tìm kiếm cây con bên trái, nếu k lớn hơn giá trị gốc, tìm kiếm cây con bên phải.
- Nếu nút có k được tìm thấy, chỉ cần trả về nút.
- Nếu k không được tìm thấy trong nút, chuyển xuống nút con bằng khóa lớn hơn.
- Nếu k không được tìm thấy trong cây, chúng tôi trả về NULL.
Chèn hoạt động
Vì B Tree là một cây tự cân bằng, bạn không thể buộc chèn một khóa vào bất kỳ nút nào.
Thuật toán sau được áp dụng:
- Chạy thao tác tìm kiếm và tìm vị trí chèn thích hợp.
- Chèn khóa mới vào vị trí thích hợp, nhưng nếu nút đã có số khóa tối đa:
- Nút, cùng với một khóa mới được chèn vào, sẽ tách ra khỏi phần tử ở giữa.
- Phần tử ở giữa sẽ trở thành phần tử cha cho hai nút con còn lại.
- Các nút phải sắp xếp lại các khóa theo thứ tự tăng dần.
|
TIỀN BOA |
Điều sau đây không đúng về thuật toán chèn: Vì nút đã đầy, do đó nó sẽ tách ra và sau đó một giá trị mới sẽ được chèn vào |
Trong ví dụ trên:
- Tìm kiếm vị trí thích hợp trong nút cho khóa
- Chèn khóa vào nút đích và kiểm tra các quy tắc
- Sau khi chèn, nút có nhiều hơn số khóa tối thiểu bằng 1? Trong trường hợp này, có, nó có. Kiểm tra quy tắc tiếp theo.
- Sau khi chèn, nút có nhiều hơn số khóa tối đa là 3? Trong trường hợp này, không, nó không. Điều này có nghĩa là Cây B không vi phạm bất kỳ quy tắc nào và việc chèn đã hoàn tất.
Trong ví dụ trên:
- Nút đã đạt đến số lượng khóa tối đa
- Nút sẽ tách ra, và khóa giữa sẽ trở thành nút gốc của hai nút còn lại.
- Trong trường hợp số khóa chẵn, nút giữa sẽ được chọn theo thiên vị trái hoặc thiên vị phải.
Trong ví dụ trên:
- Nút có ít hơn các khóa tối đa
- 1 được chèn bên cạnh 3, nhưng quy tắc thứ tự tăng dần bị vi phạm
- Để khắc phục điều này, các phím được sắp xếp
Tương tự, 13 và 2 có thể được chèn dễ dàng vào nút vì chúng đáp ứng ít hơn quy tắc khóa tối đa cho các nút.
Trong ví dụ trên:
- Nút có các khóa bằng số khóa tối đa.
- Khóa được chèn vào nút đích, nhưng nó vi phạm quy tắc về khóa tối đa.
- Nút đích được tách ra và khóa giữa theo khuynh hướng trái bây giờ là nút cha của các nút con mới.
- Các nút mới được sắp xếp theo thứ tự tăng dần.
Tương tự, dựa trên các quy tắc và trường hợp ở trên, phần còn lại của các giá trị có thể được chèn vào B Tree một cách dễ dàng.
Xóa hoạt động
Thao tác xóa có nhiều quy tắc hơn thao tác chèn và tìm kiếm.
Thuật toán sau được áp dụng:
- Chạy thao tác tìm kiếm và tìm khóa mục tiêu trong các nút
- Ba điều kiện được áp dụng dựa trên vị trí của khóa đích, như được giải thích trong các phần sau
Nếu khóa đích nằm trong nút lá
- Mục tiêu nằm trong nút lá, nhiều hơn các phím tối thiểu.
- Xóa điều này sẽ không vi phạm tài sản của B Tree
- Mục tiêu nằm trong nút lá, nó có các nút chính tối thiểu
- Xóa điều này sẽ vi phạm tài sản của B Tree
- Nút đích có thể mượn khóa từ nút bên trái ngay lập tức hoặc nút bên phải ngay lập tức (anh chị em)
- Anh chị em sẽ nói có nếu nó có nhiều hơn số khóa tối thiểu
- Khóa sẽ được mượn từ nút cha, giá trị lớn nhất sẽ được chuyển cho nút cha, giá trị lớn nhất của nút cha sẽ được chuyển sang nút đích và loại bỏ giá trị đích
- Mục tiêu nằm trong nút lá, nhưng không có anh chị em nào có số khóa nhiều hơn tối thiểu
- Tìm kiếm chìa khóa
- Hợp nhất với anh chị em và tối thiểu các nút cha
- Tổng số khóa bây giờ sẽ nhiều hơn tối thiểu
- Khóa đích sẽ được thay thế bằng nút cha tối thiểu
Nếu khóa đích nằm trong một nút nội bộ
- Chọn, theo thứ tự người tiền nhiệm hoặc người kế nhiệm theo thứ tự
- Trong trường hợp cây tiền nhiệm theo thứ tự, khóa tối đa từ cây con bên trái của nó sẽ được chọn
- Trong trường hợp kế thừa theo thứ tự, khóa tối thiểu từ cây con bên phải của nó sẽ được chọn
- Nếu khóa trước theo thứ tự của khóa đích có nhiều hơn các khóa tối thiểu, thì chỉ khi đó, nó mới có thể thay thế khóa đích bằng số tối đa của khóa trước theo thứ tự
- Nếu khóa trước theo thứ tự của khóa đích không có nhiều hơn khóa tối thiểu, hãy tìm khóa tối thiểu của khóa kế nhiệm theo thứ tự.
- Nếu khóa đích theo thứ tự tiền nhiệm và kế nhiệm đều có ít hơn khóa tối thiểu, thì hợp nhất khóa trước và khóa kế nhiệm.
Nếu khóa đích nằm trong nút gốc
- Thay thế bằng phần tử tối đa của cây con tiền nhiệm theo thứ tự
- Nếu sau khi xóa, đích có ít hơn khóa tối thiểu, thì nút đích sẽ mượn giá trị tối đa từ anh chị em của nó thông qua nút cha của anh chị em.
- Giá trị lớn nhất của cha mẹ sẽ được lấy bởi một đích, nhưng với các nút có giá trị lớn nhất của giá trị lớn nhất của cha.
Bây giờ, chúng ta hãy hiểu thao tác xóa với một ví dụ.
Sơ đồ trên hiển thị các trường hợp khác nhau của thao tác xóa trong B-Tree. B-Tree này có thứ tự 5, có nghĩa là số lượng nút con tối thiểu mà bất kỳ nút nào có thể có là 3 và số lượng nút con tối đa mà bất kỳ nút nào có thể có là 5. Trong khi đó, số lượng khóa tối thiểu và tối đa của bất kỳ nút nào. có thể có là 2 và 4, tương ứng.
Trong ví dụ trên:
- Nút đích có khóa đích để xóa
- Nút đích có số khóa nhiều hơn số khóa tối thiểu
- Đơn giản chỉ cần xóa khóa
Trong ví dụ trên:
- Nút đích có các khóa bằng các khóa tối thiểu, vì vậy không thể xóa nó trực tiếp vì nó sẽ vi phạm các điều kiện
Bây giờ, sơ đồ sau giải thích cách xóa khóa này:
- Nút đích sẽ mượn một khóa từ người anh em ngay lập tức, trong trường hợp này là khóa trước theo thứ tự (nút anh em bên trái) vì nó không có bất kỳ người kế nhiệm theo thứ tự nào (nút anh em bên phải)
- Giá trị lớn nhất của inorder tiền nhiệm sẽ được chuyển cho cha mẹ và cha mẹ sẽ chuyển giá trị lớn nhất cho nút đích (xem sơ đồ bên dưới)
Ví dụ sau minh họa cách xóa khóa cần giá trị khỏi khóa kế nhiệm theo thứ tự của nó.
- Nút đích sẽ mượn một khóa từ người anh em ngay lập tức, trong trường hợp này là người kế nhiệm theo thứ tự (người anh em bên phải) bởi vì nút tiền nhiệm theo thứ tự (người anh em bên trái) có khóa bằng với số khóa tối thiểu.
- Giá trị nhỏ nhất của phần tử kế thừa theo thứ tự sẽ được chuyển đến phần tử cha, và phần tử cha sẽ chuyển giá trị lớn nhất đến nút đích.
Trong ví dụ dưới đây, nút đích không có bất kỳ người anh em nào có thể cung cấp khóa của nó cho nút đích. Do đó, việc hợp nhất là bắt buộc.
Xem quy trình xóa khóa như vậy:
- Hợp nhất nút đích với bất kỳ anh chị em nào của nó cùng với khóa cha
- Khóa từ nút cha được chọn là anh chị em ở giữa hai nút hợp nhất
- Xóa khóa đích khỏi nút đã hợp nhất
Xóa mã giả hoạt động
private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}
Đầu ra :
Phần tử lớn nhất bị xóa khỏi B-Tree.
Tóm lược:
- B Tree là một cấu trúc dữ liệu tự cân bằng để tìm kiếm, chèn và xóa dữ liệu khỏi đĩa tốt hơn.
- B Cây được điều chỉnh bởi mức độ quy định
- B Các phím và nút của cây được sắp xếp theo thứ tự tăng dần.
- Thao tác tìm kiếm của B Tree là thao tác đơn giản nhất, thao tác này luôn bắt đầu từ gốc và bắt đầu kiểm tra xem khóa đích lớn hơn hay nhỏ hơn giá trị nút.
- Thao tác chèn của B Tree khá chi tiết, đầu tiên tìm vị trí chèn thích hợp cho khóa đích, chèn nó, đánh giá tính hợp lệ của B Tree đối với các trường hợp khác nhau, sau đó tái cấu trúc các nút B Tree cho phù hợp.
- Thao tác xóa của B Tree đầu tiên tìm kiếm khóa đích cần xóa, xóa nó, đánh giá tính hợp lệ dựa trên một số trường hợp như khóa tối thiểu và tối đa của nút đích, anh chị em và cha mẹ.