Cấu Trúc Dữ Liệu Cây M-Nhánh: Định nghĩa, thao tác và so sánh với B-Cây

Chuyên khảo phân tích Cấu trúc dữ liệu cây m nhánh vs b cây chapter05 adt m tree, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo.

• Đề tài: Cấu Trúc Dữ Liệu Cây M Nhánh Vs B Cây Chapter05 Adt M Tree

Mục lục chi tiết

• 1. CÂY M-NHÁNH
• 1.1. Định nghĩa
• 1.2. Các thao tác trên cây m-nhánh
• 1.2.1. Thao tác duyệt cây
• 1.2.1.1. Duyệt theo chiều sâu
• 1.2.1.2. Duyệt theo chiều rộng
• 1.2.2. Tìm kiếm một khóa trong cây
• 1.2.3. Thao tác thêm khóa vào cây
• 1.2.4. Xóa khóa khỏi cây
• 1.3. Bài luyện tập
• 2. B-CÂY
• 2.1. Giới thiệu
• 2.2. Định nghĩa
• 2.3. Ký hiệu và một số B-cây thông dụng
• 2.4. Thao tác thêm một phần tử
• 2.5. Xóa một khóa khỏi cây

Tóm tắt

I. Khám phá nền tảng Cấu trúc dữ liệu Cây M nhánh và B cây

Trong khoa học máy tính, việc tổ chức và truy xuất dữ liệu hiệu quả là một bài toán cốt lõi. Cấu trúc dữ liệu cây ra đời như một giải pháp mạnh mẽ, đặc biệt là các loại cây tìm kiếm. Bài viết này tập trung phân tích sâu về hai cấu trúc quan trọng: Cây M-nhánh (M-way Tree) và B-cây (B-tree). Đây là những cấu trúc nền tảng cho việc quản lý tập dữ liệu lớn, thường không thể lưu trữ hoàn toàn trong bộ nhớ chính. Cây M-nhánh, hay còn gọi là cây tìm kiếm m-phân, là một dạng tổng quát hóa của cây nhị phân tìm kiếm, cho phép mỗi nút có thể chứa nhiều hơn một khóa và có nhiều hơn hai cây con. Đặc tính này làm giảm đáng kể chiều cao của cây, từ đó giảm số lần truy cập đĩa cần thiết khi tìm kiếm. Tuy nhiên, cây M-nhánh không có cơ chế tự cân bằng, dẫn đến nguy cơ suy biến thành danh sách liên kết trong trường hợp xấu nhất, làm giảm hiệu suất tìm kiếm. Để giải quyết vấn đề này, B-cây được phát minh bởi Rudolf Bayer và Edward M. McCreight. B-cây là một dạng đặc biệt của cây M-nhánh, nhưng bổ sung các ràng buộc nghiêm ngặt để duy trì trạng thái cây cân bằng (balanced tree). Điều này đảm bảo rằng mọi nút lá đều ở cùng một độ sâu, giữ cho độ phức tạp thuật toán tìm kiếm, chèn, xóa luôn ở mức O(log n). Cả hai cấu trúc đều được định nghĩa dựa trên khái niệm Kiểu dữ liệu trừu tượng (ADT), cho phép tập trung vào các thao tác logic mà không cần quan tâm đến chi tiết cài đặt bên dưới.

1.1. Định nghĩa Cây M nhánh M way search tree là gì

Theo tài liệu của Bùi Tiến Lên (2017), một Cây M-nhánh (hay m-way search tree) được định nghĩa là một cây tìm kiếm mà mỗi nút có thể có tối đa m-1 khóa và m cây con. Các khóa trong mỗi nút được sắp xếp theo thứ tự tăng dần. Cụ thể, nếu một nút có k khóa {v1, v2, ..., vk}, nó sẽ có k+1 cây con {T1, T2, ..., Tk+1}. Các khóa trong cây con T1 sẽ nhỏ hơn v1, các khóa trong cây con Tk+1 sẽ lớn hơn vk, và các khóa trong cây con Ti (với i từ 2 đến k) sẽ nằm giữa vi-1 và vi. Cấu trúc này cho phép phân nhánh rộng hơn so với cây nhị phân, làm giảm chiều cao của cây và là tiền đề quan trọng cho các cấu trúc dữ liệu tối ưu cho lưu trữ ngoại vi.

1.2. Giới thiệu B cây Cấu trúc dữ liệu cây cân bằng ưu việt

B-cây là một phiên bản cải tiến và chuyên biệt của cây M-nhánh, được thiết kế để luôn ở trạng thái cân bằng. Một B-cây bậc m phải tuân thủ các quy tắc nghiêm ngặt: nút gốc có ít nhất 1 khóa (trừ khi cây rỗng); mỗi nút trong (không phải gốc và lá) có ít nhất ⌈m/2⌉ - 1 khóa; và tất cả các nút lá phải nằm ở cùng một độ sâu. Đặc tính cây cân bằng này là chìa khóa giúp B-cây đảm bảo hiệu suất truy vấn ổn định, ngay cả khi dữ liệu thay đổi liên tục qua các thao tác chèn xóa trên cây. Chính vì vậy, B-cây trở thành lựa chọn hàng đầu cho các ứng dụng yêu cầu truy xuất dữ liệu nhanh từ bộ nhớ ngoài.

II. Thách thức của Lưu trữ ngoại vi với cây tìm kiếm truyền thống

Các cấu trúc dữ liệu cây kinh điển như cây nhị phân tìm kiếm (BST) hay cây AVL hoạt động rất hiệu quả khi toàn bộ dữ liệu nằm trong bộ nhớ chính (RAM). Tuy nhiên, khi khối lượng dữ liệu phình to đến mức phải sử dụng lưu trữ ngoại vi (như ổ cứng HDD, SSD), các cấu trúc này bộc lộ nhiều yếu kém. Vấn đề cốt lõi nằm ở sự chênh lệch tốc độ cực lớn giữa RAM và đĩa cứng. Mỗi lần truy cập vào một nút của cây có thể tương ứng với một thao tác đọc/ghi đĩa, một hoạt động tốn kém về mặt thời gian. Với một cây nhị phân có chiều cao lớn, một thao tác tìm kiếm đơn giản có thể đòi hỏi hàng chục, thậm chí hàng trăm lần truy cập đĩa, làm cho hệ thống trở nên chậm chạp. Đây là thách thức lớn đối với các hệ quản trị cơ sở dữ liệu (DBMS) và hệ thống tệp, nơi dữ liệu thường được lưu trữ trên đĩa. Do đó, mục tiêu chính khi thiết kế cấu trúc dữ liệu cho bộ nhớ ngoài là giảm thiểu số lần truy cập đĩa. Cây M-nhánh và đặc biệt là B-cây được sinh ra để giải quyết chính xác bài toán này. Bằng cách cho phép mỗi nút lưu trữ một lượng lớn khóa và có nhiều con, chúng tạo ra những cây rất rộng và thấp. Chiều cao của cây giảm theo hàm logarit với cơ số lớn (bậc của cây), giúp giảm mạnh số lần phải đọc dữ liệu từ đĩa để đi từ nút gốc đến nút lá, tối ưu hóa quá trình đánh chỉ mục (indexing) và truy vấn.

2.1. Hạn chế của cây nhị phân khi truy xuất bộ nhớ ngoài

Cây nhị phân tìm kiếm có chiều cao O(n) trong trường hợp xấu nhất và O(log n) trong trường hợp trung bình. Khi cây cao, một thao tác tìm kiếm đòi hỏi phải đi qua nhiều nút. Mỗi nút này, nếu không nằm trong cache, sẽ yêu cầu một lần đọc đĩa. Với hàng triệu bản ghi, chiều cao của cây có thể lên đến hàng chục, dẫn đến hàng chục thao tác I/O đĩa cho một truy vấn. Các cây tự cân bằng như cây đỏ đen (red-black tree) giải quyết vấn đề chiều cao nhưng vẫn giữ cấu trúc nhị phân, không tối ưu cho việc đọc dữ liệu theo khối (block) từ đĩa.

2.2. Nhu cầu Đánh chỉ mục indexing trong cơ sở dữ liệu lớn

Trong các hệ quản trị cơ sở dữ liệu, đánh chỉ mục (indexing) là kỹ thuật sống còn để tăng tốc độ truy vấn. Index về bản chất là một cấu trúc dữ liệu phụ trợ giúp định vị nhanh chóng các bản ghi. B-cây và biến thể của nó là B+ tree là cấu trúc dữ liệu được sử dụng phổ biến nhất để triển khai index. Khả năng lưu trữ nhiều khóa trong một nút của B-cây tương ứng hoàn hảo với cách hệ điều hành đọc dữ liệu từ đĩa theo từng trang (page) hoặc khối (block), qua đó tối ưu hóa việc sử dụng băng thông I/O và giảm thiểu thời gian chờ.

III. Phương pháp vận hành Cây tìm kiếm M phân M way Tree

Cây tìm kiếm M-phân, hay M-way Tree, là một cấu trúc dữ liệu tổng quát làm nền tảng cho B-cây. Việc hiểu rõ cách thức hoạt động của nó là bước đệm quan trọng. Các thao tác cơ bản trên cây M-nhánh bao gồm duyệt, tìm kiếm, chèn và xóa. Thao tác duyệt cây có thể thực hiện theo chiều sâu (DFT) hoặc chiều rộng (BFT), tương tự như trên các đồ thị tổng quát. Trọng tâm của cây M-nhánh nằm ở thuật toán tìm kiếm trên cây. Quá trình này bắt đầu từ nút gốc và đi xuống. Tại mỗi nút, thay vì chỉ so sánh với một khóa, khóa cần tìm sẽ được so sánh với danh sách các khóa đã được sắp xếp trong nút đó (thường dùng tìm kiếm nhị phân nội bộ) để xác định cây con nào cần đi tiếp. Quá trình này lặp lại cho đến khi tìm thấy khóa hoặc gặp một cây con rỗng. Các thao tác chèn xóa trên cây M-nhánh tương đối đơn giản. Khi chèn một khóa mới, thuật toán sẽ tìm vị trí thích hợp (một nút lá). Nếu nút đó còn chỗ trống (ít hơn m-1 khóa), khóa mới sẽ được thêm vào. Tương tự, khi xóa, nếu khóa nằm ở nút lá, nó sẽ bị loại bỏ. Nếu nằm ở nút trong, nó sẽ được thay thế bằng phần tử lớn nhất của cây con trái hoặc nhỏ nhất của cây con phải. Vấn đề chính của cây M-nhánh là sự thiếu cân bằng. Các thao tác chèn xóa không có cơ chế đảm bảo chiều cao của các nhánh con được duy trì đồng đều, dẫn đến nguy cơ suy biến và ảnh hưởng đến độ phức tạp thuật toán.

3.1. Các thuật toán tìm kiếm và duyệt trên cây M nhánh

Thuật toán tìm kiếm trên cây tìm kiếm m-phân là một sự mở rộng của tìm kiếm nhị phân. Bắt đầu từ gốc, tại mỗi nút, khóa cần tìm được so sánh với m-1 khóa trong nút. Nếu tìm thấy, quá trình kết thúc. Nếu không, dựa vào kết quả so sánh, thuật toán sẽ xác định được cây con tiếp theo để đi xuống. Ví dụ, nếu khóa tìm kiếm nhỏ hơn khóa đầu tiên, thuật toán sẽ đi vào cây con ganz trái nhất. Nếu lớn hơn khóa cuối cùng, nó đi vào cây con ganz phải nhất. Nếu nằm giữa hai khóa liên tiếp, nó sẽ đi vào cây con tương ứng nằm giữa chúng.

3.2. Quy trình thao tác chèn xóa khóa trên cây M nhánh

Thao tác chèn luôn diễn ra ở một nút lá. Thuật toán tìm kiếm vị trí chèn như thể đang tìm một khóa không tồn tại. Khi đến một nút lá, nếu nút này chưa đầy (có ít hơn m-1 khóa), khóa mới được thêm vào và sắp xếp lại. Thao tác xóa phức tạp hơn một chút. Nếu khóa cần xóa ở nút lá, nó chỉ cần được gỡ bỏ. Nếu ở nút trong, nó phải được thay thế bằng một khóa phù hợp từ một nút lá (phần tử tiền nhiệm hoặc kế nhiệm) để duy trì tính chất của cây tìm kiếm, sau đó xóa khóa đó ở nút lá. Các thao tác này không xử lý các trường hợp tràn nút (node overflow) hay thiếu nút, đây là điểm khác biệt cơ bản với B-cây.

IV. Bí quyết tối ưu hiệu suất với Cấu trúc dữ liệu B cây

B-cây không chỉ là một cây tìm kiếm đa phân; nó là một cây cân bằng được thiết kế đặc biệt để tối ưu hóa hiệu suất trên bộ nhớ ngoài. Bí quyết của B-cây nằm ở các quy tắc nghiêm ngặt về số lượng khóa và con của mỗi nút, cùng với các thuật toán chèn xóa thông minh để duy trì sự cân bằng đó. Bậc của cây (order of tree), ký hiệu là m, quyết định số lượng khóa tối đa và tối thiểu trong mỗi nút. Khi thực hiện thao tác chèn, nếu việc thêm một khóa mới vào nút lá làm cho số khóa vượt quá m-1, tình trạng tràn nút (node overflow) xảy ra. Lúc này, B-cây không tạo ra một nút mới đơn giản, mà thực hiện một thao tác gọi là tách nút (node splitting). Nút bị tràn sẽ được tách thành hai nút, mỗi nút chứa khoảng một nửa số khóa, và khóa ở giữa sẽ được đẩy lên nút cha. Quá trình này có thể lan truyền lên đến tận nút gốc, và nếu gốc bị tách, một gốc mới sẽ được tạo ra, làm tăng chiều cao của cây lên một. Ngược lại, khi xóa một khóa, nếu một nút có ít hơn số khóa tối thiểu cho phép (⌈m/2⌉ - 1), tình trạng thiếu nút xảy ra. B-cây sẽ xử lý bằng hai cách: mượn khóa từ một nút anh em liền kề nếu nút đó có dư khóa, hoặc gộp nút (node merging) với một nút anh em nếu cả hai đều không đủ khóa. Những cơ chế này đảm bảo cây luôn cân bằng, giữ cho chiều cao ở mức tối thiểu và hiệu suất truy vấn luôn ổn định.

4.1. Đặc tính của cây cân bằng và Bậc của cây Order of tree

Tính chất quan trọng nhất của B-cây là tất cả các nút lá đều ở cùng một độ sâu. Điều này đảm bảo rằng thời gian tìm kiếm cho bất kỳ khóa nào cũng tương đương nhau, loại bỏ trường hợp xấu nhất như trong cây nhị phân tìm kiếm thông thường. Bậc của cây (m) là một tham số quan trọng, thường được chọn sao cho kích thước của một nút tương đương với kích thước của một trang đĩa (ví dụ: 4KB), giúp tối ưu hóa các thao tác đọc/ghi từ lưu trữ ngoại vi.

4.2. Kỹ thuật Tách nút node splitting khi chèn khóa bị tràn

Khi một nút bị tràn nút (node overflow) do chèn khóa, thuật toán tách nút được kích hoạt. Giả sử nút có m khóa. Nút sẽ được chia thành hai nút mới. Nút bên trái nhận ⌈m/2⌉ - 1 khóa đầu tiên. Nút bên phải nhận các khóa còn lại. Khóa ở chính giữa (khóa thứ ⌈m/2⌉) sẽ được đẩy lên nút cha. Thao tác này duy trì trật tự của cây và đảm bảo các nút con mới tạo đều thỏa mãn yêu cầu về số khóa tối thiểu. Nếu nút cha cũng bị tràn, quá trình tách sẽ tiếp tục lan truyền lên trên.

4.3. Kỹ thuật Gộp nút node merging và mượn khóa khi xóa

Khi xóa một khóa làm cho một nút có ít hơn số khóa tối thiểu, B-cây sẽ cố gắng 'mượn' một khóa từ nút anh em kề bên (trái hoặc phải) nếu nút đó có nhiều hơn số khóa tối thiểu. Nếu không thể mượn, thuật toán sẽ thực hiện gộp nút (node merging). Nút thiếu khóa sẽ được gộp với một nút anh em và khóa trung gian ở nút cha. Nút mới gộp lại sẽ có đủ số khóa cần thiết. Thao tác này có thể làm nút cha bị thiếu khóa, và quá trình xử lý sẽ lại lan truyền lên trên, đảm bảo toàn bộ cây luôn tuân thủ các quy tắc của B-cây.

V. Ứng dụng thực tiễn của B cây và B Tree trong CSDL

Lý thuyết về Cấu trúc dữ liệu cây M-nhánh và B-cây không chỉ dừng lại ở học thuật mà có những ứng dụng vô cùng quan trọng trong thực tế, đặc biệt là trong các hệ thống quản lý dữ liệu lớn. Hầu hết mọi hệ quản trị cơ sở dữ liệu (DBMS) hiện đại, từ Oracle, SQL Server, PostgreSQL đến MySQL (với InnoDB storage engine), đều sử dụng B-cây hoặc một biến thể phổ biến của nó là B+ tree để xây dựng cơ chế đánh chỉ mục (indexing). Khi một câu lệnh SQL yêu cầu tìm kiếm dữ liệu dựa trên một cột đã được đánh chỉ mục, hệ thống sẽ sử dụng B-cây tương ứng để nhanh chóng xác định vị trí của bản ghi trên đĩa mà không cần phải quét toàn bộ bảng. Điều này làm giảm đáng kể thời gian phản hồi của truy vấn. Hệ thống tệp (file systems) như NTFS trên Windows hay HFS+ trên macOS cũng sử dụng các cấu trúc tương tự B-cây để quản lý metadata của tệp tin, cho phép truy cập nhanh vào các tệp và thư mục. So với các cây nhị phân tự cân bằng như cây đỏ đen (red-black tree), B-cây vượt trội hơn hẳn trong môi trường lưu trữ ngoại vi do giảm thiểu được số lần truy cập đĩa. Mặc dù cây đỏ đen đảm bảo cân bằng, cấu trúc nhị phân của nó vẫn dẫn đến chiều cao lớn hơn và không tận dụng được cơ chế đọc dữ liệu theo khối của ổ đĩa.

5.1. B cây trong Hệ quản trị cơ sở dữ liệu và hệ thống tệp

Trong DBMS, B-cây được dùng để tạo chỉ mục cho các khóa chính và các cột được truy vấn thường xuyên. Mỗi nút của B-cây thường được thiết kế để vừa với một trang (page) của bộ nhớ đệm (buffer cache), thường là 4KB hoặc 8KB. Khi cần tìm một khóa, DBMS chỉ cần đọc một vài trang đĩa để đi từ gốc đến lá, một cải tiến vượt bậc so với việc phải đọc hàng ngàn khối dữ liệu nếu không có chỉ mục. Tương tự, trong hệ thống tệp, B-cây giúp quản lý việc phân bổ các khối đĩa cho tệp tin, giúp tìm kiếm và truy cập tệp hiệu quả.

5.2. So sánh B cây với Cây đỏ đen red black tree và B Tree

Cây đỏ đen phù hợp cho các cấu trúc dữ liệu trong bộ nhớ chính (in-memory), nơi chi phí truy cập mỗi nút là như nhau và thấp. Ngược lại, B-cây được tối ưu cho bộ nhớ ngoài. B+ tree là một biến thể quan trọng của B-cây. Trong B+ tree, tất cả các khóa chỉ được lưu ở các nút lá, còn các nút trong chỉ chứa các khóa định tuyến. Thêm vào đó, tất cả các nút lá được liên kết với nhau bằng một danh sách liên kết. Cấu trúc này giúp tối ưu hóa các truy vấn duyệt theo khoảng (range queries) và quét toàn bộ chỉ mục, làm cho nó trở thành lựa chọn phổ biến hơn cả B-cây trong các hệ cơ sở dữ liệu hiện đại.