Các tài liệu về B+ tree toàn bằng tiếng Anh (Kể cả của thầy và cả trên Internet, có google cũng không có bản tiếng Việt nào nên hồn) thôi thì gõ một ít ra đây để tiện trao đổi. Một số bạn có hỏi gì thì hỏi lên diễn đàn, đừng có bom vào thùng thư của tôi, mỗi ngày nhận tới vài trăm thư, nên tôi chỉ đọc những thư quan trọng thôi còn lại là AutoDelete, nên hết sức thông cảm.
Tiện thể nhắc luôn mấy cái anh chàng và cô nàng không chịu đọc kỹ, mà đã nhắc lại nhiều lần rồi là đã ở nhóm "Học viên DS" thì đừng có đòi tham gia vào nhóm khác (Thành viên đọc được mọi thứ) vì có tham gia vào thì sẽ đảo bit = 0 sẽ bị cấm không đọc được đâu. Đã nhắc đi nhắc lại rồi mà vẫn cứ lao đầu xin chết thì cũng lạ đấy nhé.

Thôi năm mới nói tý cho vui, gõ một ít về bài học cho những người lười học thì lên đây đọc. Mà nói thật là nếu cứ học kiểu này có khi phải thuê bạn Hải Yến ở trường Mầm Non Hoa Phượng Đỏ học hộ và thi hộ mất thôi.

B+ Tree là một cấu trúc dữ liệu dạng cây ‘đa phân cân bằng’. Cấu trúc một node của nó thường được chia làm nhiều phần. Cây được tổ chức với một qui tắc nhất định được tạo ra từ đầu. Thường thì giá trị của các node tăng dần từ trái qua phải, node con bên trái sẽ chứa giá trị nhỏ hơn node con bên phải...

[You must be registered and logged in to see this image.]

B + Tree là một sự tổng quát hóa của cây nhị phân tìm kiếm (BST). Sự khác biệt chính giữa chúng là số lượng node con của B+Tree nó sẽ nhiều hơn chứ không bị giới hạn bởi hai phần tử như của cây nhị phân tìm kiếm. Mục tiêu ở đây là làm sao để giảm tối đa số lần truy xuất các thiết bị ngoại vi (ở đây là đĩa). Tại bất cứ thời điểm nào chúng ta sẽ thử định vị những bản ghi, chúng ta muốn độ cao của cây đa phân này phải là nhỏ nhất để giảm chi phí tìm kiếm, để đạt được mục tiêu này thì số lượng nhánh trong cây phải lớn.

Nếu B+Tree có bậc là m thì môt node của nó sẽ có tối đa m nhánh con và có m-1 khóa để tìm kiếm.

• Các record chỉ được lưu ở nút lá của cây

• Tất cả các nút (ngoại trừ nút gốc) có tối thiểu là m/2 (ở đây phép chia nguyên làm tròn về phía trên, nếu lẻ) và tối đa là m nhánh con.

• Nút gốc và lá phải ít nhất có 2 con.

• Bên trong một node lưu giá trị tìm kiếm, một vài khóa được sử dụng như những “người chỉ đường” cho quá trình tìm kiếm. Những khóa này cần phải được sắp xếp theo môt thứ tự thống nhất trừ trước (tăng dần từ trái qua phải).

• Tùy thuộc vào kích thước của một record so với kích thước của một khóa thì node lá của B+Tree bậc m có thể lưu nhiều hơn hoặc ít hơn m records. Thông thường kích thước của một node là bội số của một khối dữ liệu trong ổ đĩa (bên windows mặc định là 512byte).

• Các node lá của cây thường được liên kết với nhau để tạo thành một danh sách liên kết, điều này nhằm mục tiêu là để không phải duyệt trở lại node gốc trong quá trình duyệt tìm kiếm.

Ví dụ một cây B+Tree:
[You must be registered and logged in to see this image.]

Các đề tham khảo về câu dạng này:
1. Hãy cho biết kết quả của các thao tác sau khi thực hiện tren cây B-Tree với bậc m=5(vẽ cây minh họa từng bước) khi lần lượt thêm các khóa sau vào cây: 15, 35, 26, 18, 22, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 11, 97, 48, 63, 78, 20.

2. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 7, 67, 43, 45, 50, 99, 95, 70, 75, 55, 60, 8, 12, 5, 3, 20, 22, 15, 26, 65, 80,30, 40,19, 57, 89. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

3. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 13, 5, 8, 11, 65, 1, 45, 33, 87, 21, 4, 55, 20, 34, 39, 32, 90, 56, 43, 68, 59, 49, 23, 47, 14, 24. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

4. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 5, 34, 22, 1, 32, 6, 7, 23, 45, 56, 3, 89, 51, 59, 33, 50, 9, 46, 83, 11, 19, 65, 49, 43, 38, 17, 92, 27, 82. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
b. Cho biết kết quả cuối cùng cua B+-tree lần lượt thêm các khóa ở câu a.

5. a Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 20, 78, 63, 48, 97, 11, 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 22, 18, 26, 35, 15, 82, 92, 3, 51. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
b. Cho biết kết quả cuối cùng cua B+-tree (m=5) tuong ứng với cây B-Tree ở câu a.

6. a.Cho cây B-Tree với bậc m=6. Lần lượt thêm các khóa sau vào cây: 57, 21, 34, 15, 58, 47, 94, 17, 46, 11, 49, 86, 82, 20, 99, 48, 95, 44, 55, 38, 63, 66, 59, 39, 78, 16, 68, 64, 90, 112, 135, 104 và 10. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
b.Cho biết kết quả cuối cùng cua B+-tree lần lược thêm các khóa ở câu a.

7. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 56, -54, 84, 75, 48, 59, 83, -96, 67, -90, 85, 89, 90, 13, 9, 68, 25, 60, 5, 19, 52, 21, 28, 66, 45, 4, 50, 64, 24, 37, 47, -78, -76, 87, 2, 54, 81, 17, -42, 6, 74. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
b. Trình bày tiến trình khi lần lược xóa khóa -42 và 25.

Đại ca đưa lời giải luôn nhé.

Theo em, đặc điểm quan trọng nhất của B tree là:
1. Có các record, và các record chỉ được lưu ở nút lá của cây

2. Khi chia nút ra, thì khác với cây B, là nút giữa được copy 1 lần đẩy lên trên. Tức là có 2 phiên bản giá trị khoá (1 ở lá và 1 ở nút con). Sở dĩ như vậy vì nút con không có record, nên nó được đẩy lên làm khoá tìm kiếm, còn nút lá vẫn là đầu mối quan trọng để tìm và liên kết với nhau.

3. Các nút lá liên kết với nhau theo dạng xâu liên kết. Nên ta có thể tìm luôn trên lá mà không cần phải quay ngược lên trên để tìm (Theo lý thuyết). Tuy nhiên việc tìm trên lá sẽ mất nhiều thời gian hơn do truy cập bộ nhớ ngoài (Còn tìm trên cây là tìm trong RAM) nên khi thầy có hỏi đừng có ngốc nghếch mà bảo tìm trên lá nhanh hơn, kẻo lại bị đánh giá là ... chẳng hiểu gì cả.

Thắng BK đã viết:Đại ca đưa lời giải luôn nhé.

Cài Java vào đây thêm từng node vào nó sẽ thêm hộ, rồi chép ra:
[You must be registered and logged in to see this link.]

Cây B+ phải được ép vào trong khuôn khổ quy tắc của nó. Nó khác thường ở chỗ nào?

- Nó khác thường ở chỗ không phải mỗi nút có thể cho phép chỉ một khoá. Mà số khoá trên mỗi nút phụ thuộc vào bậc của cây. Ví dụ người ta cho bậc của cây là b chẳng hạn, thì các nút con phải có tối thiểu b/2 khoá và có tối đa b khoá. Hay số lượng khoá của mỗi nút là m thì, m phải nằm trong khoảng [You must be registered and logged in to see this image.] . Khi số khoá mà nhỏ hơn b/2 thì đương nhiên phải gộp nút cho nó lớn hơn b/2. Và đương nhiên khi số khoá lớn hơn thì phải tách nút thành 2 nút con.
- Nút gốc đặc biệt nên cho phép tối thiểu là 1 khoá.
Bây giờ ta xem lại cái bảng sau nhé:
Kiểu NodeKiểu conSố con tối thiểuSố con tối đa Ví dụ minh hoạ b = 7Ví dụ minh hoạ b = 100

Nút gốc	Keys	1	b	1 - 7	1 - 100
Nút gốc	Nút trong hoặc nút lá	2	b	2 - 7	2 - 100
Nút trong	Nút trong hoặc nút lá	[You must be registered and logged in to see this image.]	b	4 - 7	50 - 100
Nút lá	Keys	[You must be registered and logged in to see this image.]	b - 1	3 - 6	50 - 99

Với 1 cây bậc b và có chiều cao h:

• Số lượng records tối đa có thể lưu được: n_max = b^h − b^{h − 1}
  

• Số lượng records tối thiểu có thể lưu được:[You must be registered and logged in to see this image.]
  

• Số lượng khoá tối thiểu là: [You must be registered and logged in to see this image.]
  

• Việc lưu trữ cây O(n)
  
• Thao tác chèn 1 record O(log _bn)
  
• Thao tác tìm 1 record O(log _bn)
  
• Loại bỏ 1 record O(log _bn)
  
• Truy vấn với k phần tử trong giới hạn yêu cầu O(log _bn + k)
  
• Truy vấn phân trang với trang cỡ s và số trang p yêu cầu O(p * s)
  

Ban HaiYen đưa ra cái view quá tuyệt vời, chẳng cần đọc, chỉ cần nhìn cũng hiểu qua đường link bạn cung cấp [You must be registered and logged in to see this link.]

Admin đã viết:Các đề tham khảo về câu dạng này:
1. Hãy cho biết kết quả của các thao tác sau khi thực hiện tren cây B-Tree với bậc m=5(vẽ cây minh họa từng bước) khi lần lượt thêm các khóa sau vào cây: 15, 35, 26, 18, 22, 42, 13, 46, 27, 8, 32, 38, 24, 45, 25, 11, 97, 48, 63, 78, 20.

2. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 7, 67, 43, 45, 50, 99, 95, 70, 75, 55, 60, 8, 12, 5, 3, 20, 22, 15, 26, 65, 80,30, 40,19, 57, 89. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

3. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 13, 5, 8, 11, 65, 1, 45, 33, 87, 21, 4, 55, 20, 34, 39, 32, 90, 56, 43, 68, 59, 49, 23, 47, 14, 24. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.

4. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 5, 34, 22, 1, 32, 6, 7, 23, 45, 56, 3, 89, 51, 59, 33, 50, 9, 46, 83, 11, 19, 65, 49, 43, 38, 17, 92, 27, 82. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
b. Cho biết kết quả cuối cùng cua B+-tree lần lượt thêm các khóa ở câu a.

5. a Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 20, 78, 63, 48, 97, 11, 25, 45, 24, 38, 32, 8, 27, 46, 13, 42, 22, 18, 26, 35, 15, 82, 92, 3, 51. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
b. Cho biết kết quả cuối cùng cua B+-tree (m=5) tuong ứng với cây B-Tree ở câu a.

6. a.Cho cây B-Tree với bậc m=6. Lần lượt thêm các khóa sau vào cây: 57, 21, 34, 15, 58, 47, 94, 17, 46, 11, 49, 86, 82, 20, 99, 48, 95, 44, 55, 38, 63, 66, 59, 39, 78, 16, 68, 64, 90, 112, 135, 104 và 10. Trình bày tiến trình khi lần lượt thêm từng khóa trên vào cây.
b.Cho biết kết quả cuối cùng cua B+-tree lần lược thêm các khóa ở câu a.

7. a. Cho cây B-Tree với bậc m=5. Lần lượt thêm các khóa sau vào cây: 56, -54, 84, 75, 48, 59, 83, -96, 67, -90, 85, 89, 90, 13, 9, 68, 25, 60, 5, 19, 52, 21, 28, 66, 45, 4, 50, 64, 24, 37, 47, -78, -76, 87, 2, 54, 81, 17, -42, 6, 74. Trình bày tiến trình khi lần lược thêm từng khóa trên vào cây.
b. Trình bày tiến trình khi lần lược xóa khóa -42 và 25.

Cho đề sao hok cho lời giải trời vậy cho đề làm gì hả

Admin đã viết:Các tài liệu về B+ tree toàn bằng tiếng Anh (Kể cả của thầy và cả trên Internet, có google cũng không có bản tiếng Việt nào nên hồn) thôi thì gõ một ít ra đây để tiện trao đổi. Một số bạn có hỏi gì thì hỏi lên diễn đàn, đừng có bom vào thùng thư của tôi, mỗi ngày nhận tới vài trăm thư, nên tôi chỉ đọc những thư quan trọng thôi còn lại là AutoDelete, nên hết sức thông cảm.
Tiện thể nhắc luôn mấy cái anh chàng và cô nàng không chịu đọc kỹ, mà đã nhắc lại nhiều lần rồi là đã ở nhóm "Học viên DS" thì đừng có đòi tham gia vào nhóm khác (Thành viên đọc được mọi thứ) vì có tham gia vào thì sẽ đảo bit = 0 sẽ bị cấm không đọc được đâu. Đã nhắc đi nhắc lại rồi mà vẫn cứ lao đầu xin chết thì cũng lạ đấy nhé.

Thôi năm mới nói tý cho vui, gõ một ít về bài học cho những người lười học thì lên đây đọc. Mà nói thật là nếu cứ học kiểu này có khi phải thuê bạn Hải Yến ở trường Mầm Non Hoa Phượng Đỏ học hộ và thi hộ mất thôi.

B+ Tree là một cấu trúc dữ liệu dạng cây ‘đa phân cân bằng’. Cấu trúc một node của nó thường được chia làm nhiều phần. Cây được tổ chức với một qui tắc nhất định được tạo ra từ đầu. Thường thì giá trị của các node tăng dần từ trái qua phải, node con bên trái sẽ chứa giá trị nhỏ hơn node con bên phải...

[You must be registered and logged in to see this image.]

B + Tree là một sự tổng quát hóa của cây nhị phân tìm kiếm (BST). Sự khác biệt chính giữa chúng là số lượng node con của B+Tree nó sẽ nhiều hơn chứ không bị giới hạn bởi hai phần tử như của cây nhị phân tìm kiếm. Mục tiêu ở đây là làm sao để giảm tối đa số lần truy xuất các thiết bị ngoại vi (ở đây là đĩa). Tại bất cứ thời điểm nào chúng ta sẽ thử định vị những bản ghi, chúng ta muốn độ cao của cây đa phân này phải là nhỏ nhất để giảm chi phí tìm kiếm, để đạt được mục tiêu này thì số lượng nhánh trong cây phải lớn.

Nếu B+Tree có bậc là m thì môt node của nó sẽ có tối đa m nhánh con và có m-1 khóa để tìm kiếm.

• Các record chỉ được lưu ở nút lá của cây

• Tất cả các nút (ngoại trừ nút gốc) có tối thiểu là m/2 (ở đây phép chia nguyên làm tròn về phía trên, nếu lẻ) và tối đa là m nhánh con.

• Nút gốc và lá phải ít nhất có 2 con.

• Bên trong một node lưu giá trị tìm kiếm, một vài khóa được sử dụng như những “người chỉ đường” cho quá trình tìm kiếm. Những khóa này cần phải được sắp xếp theo môt thứ tự thống nhất trừ trước (tăng dần từ trái qua phải).

• Tùy thuộc vào kích thước của một record so với kích thước của một khóa thì node lá của B+Tree bậc m có thể lưu nhiều hơn hoặc ít hơn m records. Thông thường kích thước của một node là bội số của một khối dữ liệu trong ổ đĩa (bên windows mặc định là 512byte).

• Các node lá của cây thường được liên kết với nhau để tạo thành một danh sách liên kết, điều này nhằm mục tiêu là để không phải duyệt trở lại node gốc trong quá trình duyệt tìm kiếm.

Ví dụ một cây B+Tree:
[You must be registered and logged in to see this image.]

xùy cái ví dụ cùi bắp hok bit lượm ở đâu nhìn dek có hiêu gì hết