B TREE trong cấu trúc dữ liệu: Tìm kiếm, chèn, xóa Operaví dụ

Quy tắc cho cây B

Dưới đâ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 cấp độ.
• B-Tree được xác định bởi một số mức độ, còn được gọi là “thứ tự” (được xác định bởi một tác nhân bên ngoài, giống như một lập trình viên), được gọi là

  m

  trở đi. Giá trị của

  m

  phụ thuộc vào kích thước khối trên đĩa nơi 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 nút con tối đa, 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 = 4
  max keys: 4 – 1 = 3
  

• Mỗi nút, ngoại trừ nút gốc, phải chứa các khóa tối thiểu của

  [m/2]-1

  Ví dụ:

  m = 4
  min keys: 4/2-1 = 1
  

• Số nút con tối đa mà một nút có thể có bằng với bậc của nó, tức là

  m

• Số lượng con tối thiểu mà một nút có thể có là một nửa đơn hàng, tức là m/2 (giá trị trần được lấy).
• 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 nên sử dụng B-Tree

Dưới đây là lý do sử dụng B-Tree

• Giảm số lần đọc được thực hiện trên đĩa
• B Cây có thể dễ dàng được tối ưu hóa để điều chỉnh kích thước của nó (tức 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 tin.
• Một lựa chọn tốt để lựa chọn khi đọc và ghi khối dữ liệu lớn

Lịch sử cây B

• Dữ liệu được lưu trên đĩa theo khối, dữ liệu này khi đưa vào bộ nhớ chính (hoặc RAM) 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 đòi hỏi phải đọ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 để lưu tham chiếu bản ghi của các bản ghi dựa trên các khối chứa chúng. Điều này giúp giảm đáng kể thời gian và mức tiêu thụ bộ nhớ.
• Vì có dữ liệu khổng lồ nên chúng ta 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 để sắp xếp dữ liệu theo kiểu tự cân bằng.

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

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 đây được áp dụng:

• Đặt 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 dưới theo cách đệ quy.
• Nếu k nhỏ hơn giá trị gốc thì tìm cây con bên trái, nếu k lớn hơn giá trị gốc thì tìm cây con bên phải.
• Nếu nút có k tìm thấy, chỉ cần trả lại nút.
• Nếu k không được tìm thấy trong nút, hãy duyệt xuống nút con bằng khóa lớn hơn.
• Nếu không tìm thấy k trong cây, chúng ta trả về NULL.

Chèn Operasản xuất

Vì Cây B là cây tự cân bằng nên bạn không thể ép buộc chèn khóa vào bất kỳ nút nào.

Thuật toán sau đây đượ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ố lượng khóa tối đa:
• Nút cùng với khóa mới được chèn sẽ tách ra khỏi phần tử ở giữa.
• Phần tử ở giữa sẽ trở thành nút cha của 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.

TIP	Câu sau đây không đúng về thuật toán chèn: Vì nút đã đầy nên 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 để tìm khóa
• Chèn khóa vào nút đích và kiểm tra quy tắc
• Sau khi chèn, nút có nhiều hơn số lượng khóa tối thiểu là 1 không? Trong trường hợp này, đúng vậy. Kiểm tra quy tắc tiếp theo.
• Sau khi chèn, nút có nhiều hơn số lượng khóa tối đa là 3 không? 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à quá trình 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ẽ phân chia 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ố phím chẵn thì nút ở giữa sẽ được chọn theo độ lệch trái hoặc độ lệch phải.

Trong ví dụ trên:

• Nút có ít hơn số khóa tối đa
• 1 được chèn vào 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 quy tắc khóa ít hơn tối đa cho các nút.

Trong ví dụ trên:

• Nút có các khóa bằng với các khóa tối đa.
• Khóa được chèn vào nút đích nhưng vi phạm quy tắc khóa tối đa.
• Nút mục tiêu được phân chia và khóa giữa theo độ lệch trái hiện 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, các giá trị còn lại có thể được chèn dễ dàng vào Cây B.

Xóa bỏ Operasản xuất

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 đây đượ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 mục tiêu, như được giải thích trong các phần sau

Nếu khóa mục tiêu nằm ở nút lá

• Target nằm trong nút lá, nhiều hơn các khóa tối thiểu.
• Việc xóa đi sẽ không vi phạm thuộc tính của B Tree
• Target nằm trong nút lá, nó có các nút khóa tối thiểu
• Xóa cái này sẽ vi phạm thuộc tính của B Tree
• Target nút có thể mượn khóa từ nút ngay bên trái hoặc nút bên phải ngay lập tức (anh chị em)
• Anh chị em sẽ nói Vâng nếu nó có nhiều hơn số lượng khóa tối thiểu
• Khóa sẽ được mượn từ nút cha, giá trị tối đa sẽ được chuyển cho nút cha, giá trị tối đa của nút cha sẽ được chuyển đến nút đích và xóa giá trị đích
• Target nằm trong nút lá, nhưng không có anh chị em nào có số lượng 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ẽ lớn hơn tối thiểu
• Khóa mục tiêu sẽ được thay thế bằng mức tối thiểu của nút cha

Nếu khóa mục tiêu nằm trong một nút bên trong

• Hoặc chọn, người tiền nhiệm theo thứ tự hoặc người kế nhiệm theo thứ tự
• Trong trường hợp tiền thân theo thứ tự thì 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 mục tiêu 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 mục tiêu bằng khóa 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 mục tiêu 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ế tiếp theo thứ tự.
• Nếu cả khóa trước và khóa kế tiếp theo thứ tự của khóa mục tiêu đều có ít hơn khóa tối thiểu thì hãy hợp nhất khóa trước và khóa kế tiếp.

Nếu khóa mục tiêu nằm ở nút gốc

• Thay thế bằng phần tử lớn nhất của cây con trước đó theo thứ tự
• Nếu sau khi xóa, nút mục tiêu có ít hơn khóa tối thiểu thì nút mục tiêu sẽ mượn giá trị tối đa từ nút anh chị em của nó thông qua nút cha của nút anh chị em.
• Giá trị tối đa của nút cha sẽ được lấy bởi một mục tiêu, nhưng với các nút có giá trị tối đa của nút anh chị em.

Bây giờ, hãy hiểu thao tác xóa bằng một ví dụ.

Sơ đồ trên hiển thị các trường hợp thao tác xóa khác nhau trong Cây B. Cây B này có thứ tự 5, có nghĩa là số nút con tối thiểu mà bất kỳ nút nào cũng có thể có là 3 và số nút con tối đa mà bất kỳ nút nào cũng có thể có là 5. Trong khi đó, số lượng khóa tối thiểu và tối đa mà bất kỳ nút nào cũng có thể có là 2. có thể có lần lượt là 4 và XNUMX.

Trong ví dụ trên:

• Nút đích có khóa mục tiêu để xóa
• Nút đích có nhiều khóa hơn số khóa tối thiểu
• Đơn giản chỉ cần xóa chìa khóa

Trong ví dụ trên:

• Nút đích có khóa bằng khóa tối thiểu nên không thể xóa trực tiếp vì sẽ vi phạm điều kiện

Bây giờ, sơ đồ sau đây giải thích cách xóa khóa này:

• Nút mục tiêu sẽ mượn khóa từ nút kế nhiệm ngay lập tức, trong trường hợp này là nút kế nhiệm theo thứ tự (anh chị em bên trái) vì nó không có bất kỳ nút kế nhiệm theo thứ tự nào (anh chị em bên phải)
• Giá trị tối đa của nút tiền thân theo thứ tự sẽ được chuyển cho nút cha và nút cha sẽ chuyển giá trị tối đa cho nút đích (xem sơ đồ bên dưới)

Ví dụ sau đây minh họa cách xóa khóa cần có giá trị từ khóa kế nhiệm theo thứ tự của nó.

• Nút mục tiêu sẽ mượn một khóa từ nút anh chị em trực tiếp, trong trường hợp này là nút kế thừa theo thứ tự (anh chị em bên phải) vì nút kế nhiệm theo thứ tự (anh chị em bên trái) có các khóa bằng các khóa tối thiểu.
• Giá trị tối thiểu của nút kế thừa theo thứ tự sẽ được chuyển cho nút cha và nút cha sẽ chuyển giá trị tối đa cho nút mục tiêu.

Trong ví dụ bên dưới, nút mục tiêu không có bất kỳ nút anh em nào có thể trao khóa của nó cho nút mục tiêu. Vì vậy, việc sáp nhập là cần thiết.

Xem quy trình xóa khóa như vậy:

• Hợp nhất nút mục tiêu với bất kỳ nút anh chị em trực tiếp nào của nó cùng với khóa cha
• Khóa từ nút cha được chọn là anh em ở giữa hai nút hợp nhất
• Xóa khóa mục tiêu khỏi nút đã hợp nhất

Xóa bỏ OperaMã giả

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        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ổng kết

• B Tree là 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 quy định theo mức độ quy định
• B Các khóa và nút cây được sắp xếp theo thứ tự tăng dần.
• Hoạt động tìm kiếm của B Tree là hoạt động đơn giản nhất, luôn bắt đầu từ gốc và bắt đầu kiểm tra xem khóa mục tiêu lớn hơn hay nhỏ hơn giá trị nút.
• Hoạt động chèn của Cây B khá chi tiết, đầu tiên là tìm vị trí chèn thích hợp cho khóa mục tiêu, chèn nó, đánh giá tính hợp lệ của Cây B trong các trường hợp khác nhau, sau đó cơ cấu lại các nút Cây B cho phù hợp.
• Thao tác xóa của Cây B trước tiên tìm kiếm khóa mục tiêu 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 mục tiêu, anh chị em và cha mẹ.