›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - B-cây - Đậu Ngọc Hà Dương

pptx 81 trang Gia Huy 16/05/2022 3750
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - B-cây - Đậu Ngọc Hà Dương", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pptxbai_giang_cau_truc_du_lieu_va_giai_thuat_b_cay_dau_ngoc_ha_d.pptx

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - B-cây - Đậu Ngọc Hà Dương

  1. Giảng viên: Đậu Ngọc Hà Dương
  2. 2 Cây tìm kiếm m-nhánh B-Cây Các thao tác trên B-cây Cây B+ Đọc thêm: Tập tin chỉ mục IDX trong FoxPro Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  3. 3 m-way search tree m-way tree Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  4. 4  Cây tìm kiếm m-nhánh là cây có tính chất:  Có tối đa m-1 khóa trong mỗi node (v1, v2, , vk) (k m-1).  Các giá trị khóa trong node được tổ chức có thứ tự (v1 < v2 < < vk).  Một node có k khóa thì sẽ có k + 1 cây con (các cây con có thể rỗng). ◼ Các cây con đặt giữa hai giá trị khóa. ◼ Hai cây con nằm ở hai đầu của dãy khóa ◼ Mỗi khóa sẽ có cây con trái và cây con phải. ◼ Các giá trị của cây con trái sẽ nhỏ hơn giá trị của khóa. ◼ Các giá trị của cây con phải sẽ lớn hơn giá trị của khóa. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  5. 5 16 25 10 14 20 33 42 11 28 49 Cây tìm kiếm 3-nhánh Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  6. 6  Tìm kiếm  Thêm phần tử  Xóa phần tử Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  7. 7  Tổng quát hóa từ trường hợp cây nhị phân tìm kiếm  X là giá trị cần tìm  Nếu X vk thì tìm X bên nhánh phải của vk.  Nếu X = vi thì thông báo tìm thấy.  Nếu vi < X < vi+1 thì tìm X tại cây con nằm giữa vi và vi+1. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  8. 8  Tổng quát hóa từ trường hợp cây nhị phân tìm kiếm  X là giá trị cần thêm vào cây.  Duyệt cây tìm X trên cây. ◼ Nếu X đã tồn tại trên cây thì không thêm. ◼ Nếu X chưa tồn tại (tìm thấy node rỗng) thì ◼ Nếu node cha (của node rỗng tìm thấy) còn có thể thêm X vào thì thêm X vào node cha. ◼ Ngược lại, tạo node mới và thêm X vào node đó. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  9. 9 16 25 10 14 20 33 42 11 13 28 49 Thêm vào giá trị 13 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  10. 10 16 25 10 14 20 33 42 11 28 37 49 Thêm vào giá trị 37 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  11. 11  Tương tự cây nhị phân tìm kiếm  Tìm vị trí của phần tử X cần xóa.  Nếu X nằm giữa hai cây con rỗng thì xóa X.  Nếu X có cây con, thay thế X bằng: ◼ Phần tử lớn nhất bên cây con trái của X hoặc ◼ Phần tử nhỏ nhất bên cây con phải của X Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  12. 12 16 25 10 14 20 33 42 11 28 49 Xóa giá trị 20 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  13. 13 16 25 10 14 33 42 11 28 49 Xóa giá trị 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  14. 14 16 28 10 14 33 42 11 25 49 Xóa giá trị 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  15. 15 16 28 10 14 33 42 11 49 Xóa giá trị 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  16. 16 B-tree Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  17. 17  B-cây bậc m là 1 cây tìm kiếm m-nhánh (m>2) thỏa:  Nút gốc có ít nhất 1 khóa  Tất cả các cây con rỗng ở cùng một mức.  Tất cả các node (trừ node gốc) có ít nhất m/2 cây con (có ít nhất m/2 -1 khóa).  Giá trị m thường là lẻ. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  18. 18 26 Một B-cây có bậc là 5 6 12 42 51 62 1 2 4 7 8 13 15 18 25 27 29 45 46 48 53 55 60 64 70 90 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  19. 19 26 Có phải là B-cây? 6 12 42 51 62 1 2 4 13 15 18 25 27 29 45 46 48 53 55 60 64 70 90 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  20. 20  Gọi độ cao của cây: h h+1  Số khóa tối đa của B-cây bậc m: m −1 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  21. 21  Tìm kiếm  Thực hiện tương tự trên cây tìm kiếm m-nhánh.  Thêm phần tử (khóa)  Xóa phần tử (khóa) Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  22. 22  Thêm phần tử (khóa) vào node lá.  Nếu node lá bị tràn thì  Tách thành 2 node mới.  Khóa chính giữa được đưa lên node cha.  Thực hiện tương tự nếu node cha bị tràn.  Nếu node gốc bị tràn thì tạo một node gốc mới (có 1 khóa duy nhất là khóa chính giữa của node cũ) Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  23. 23  Tạo B-cây bậc 5 gồm các phần tử theo thứ tự sau:  1, 12, 8, 2, 25, 5, 14, 28, 17, 7, 52, 16, 48, 68, 3, 26, 29, 53, 55, 45 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  24. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 24 1 1282 128 12 Thêm 1 Thêm 12 Thêm 8 Thêm 2 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  25. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 25 1 2 128 12 25 8 1 2 12 25 Thêm 25 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  26. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 26 8 1 2 5 12 14 25 28 Thêm 5, 14, 28 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  27. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 27 8 1 2 5 12 14 17 25 28 8 17 1 2 5 12 14 25 28 Thêm 17 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  28. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 28 8 17 1 2 5 12 14 25 28 8 17 1 2 5 7 12 14 16 25 28 48 52 Thêm 7, 52, 16, 48 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  29. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 29 8 17 1 2 5 7 12 14 16 25 28 48 52 68 8 17 48 1 2 5 7 12 14 16 25 28 52 68 Thêm 68 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  30. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 30 8 17 48 1 2 3 5 7 12 14 16 25 28 52 68 3 8 17 48 1 2 5 7 12 14 16 25 28 52 68 Thêm 3 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  31. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 31 3 8 17 48 1 2 5 7 12 14 16 25 26 28 29 52 53 55 68 Thêm 26, 29, 53, 55 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  32. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 32 3 8 17 48 1 2 5 7 12 14 16 25 26 28 29 45 52 53 55 68 3 8 17 28 48 1 2 5 7 12 14 16 25 26 29 45 52 53 55 68 Thêm 45 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  33. 1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45 33 3 8 17 28 48 1 2 5 7 12 14 16 25 26 29 45 52 53 55 68 17 3 8 28 48 1 2 5 7 12 14 16 25 26 29 45 52 53 55 68 Thêm 45 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  34. 34  Tạo B-cây bậc 5 gồm các khóa theo thứ tự nhập sau đây: 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  35. 35  Thực hiện tương tự cây tìm kiếm m-nhánh.  Xét hai trường hợp:  Khóa thuộc node lá  Khóa thuộc node trong Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  36. 36  Khóa thuộc node lá:  Xóa khóa khỏi node chứa khóa.  Sau khi xóa, nếu node chứa khóa mới xóa có số khóa không đủ (ít hơn m/2 -1 khóa) thì: ◼ Mượn khóa từ node bên cạnh (Node bên cạnh dư khóa). ◼ Nhập khóa với node bên cạnh cùng với khóa cha (Node bên cạnh KHÔNG dư khóa). Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  37. 37  Khóa thuộc node trong:  Khóa bị xóa có các node bên nhánh con trái và nhánh con phải có số khóa tối thiểu ( m/2 -1 khóa): nhập khóa của 2 node con.  Ngược lại: tìm phần tử thế mạng và thực hiện cân bằng lại cây như trường hợp xóa khóa thuộc node lá. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  38. 38  Sau khi xóa khóa dẫn đến việc các node trong cây bị thiếu khóa: cân bằng lại cây từ dưới lên.  TH1: Nếu node kề phải dư khóa ◼ Thêm khóa cha của 2 node vào node bị thiếu. ◼ Lấy khóa đầu của node kề phải lên thay cho khóa cha ở node cha.  TH2: Nếu node kề trái dư khóa: làm tương tự trường hợp trên  TH3: Nếu cả node kề trái và phải đều không dư khóa: ◼ Tạo node mới chứa khóa của node bị thiếu, tất cả khóa của 1 node kề nó và khóa cha của 2 node này. ◼ Xóa khóa cha của 2 node ở node cha, và thay 2 node con vừa bị nhập bằng node mới tạo. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  39. 39  Cho B-cây bậc 5: 12 29 52 2 7 9 15 22 31 43 56 69 72 Xóa khóa 2 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  40. 40  Cho B-cây bậc 5: 12 29 52 7 9 15 22 31 43 56 69 72 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  41. 41  Cho B-cây bậc 5: 12 29 52 7 9 15 22 31 43 56 69 72 Xóa khóa 52 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  42. 42  Cho B-cây bậc 5: 12 29 56 7 9 15 22 31 43 52 69 72 Xóa khóa 52. Thay thế bằng 56 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  43. 43  Cho B-cây bậc 5: 12 29 56 7 9 15 22 31 43 69 72 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  44. 44  Cho B-cây bậc 5: 12 29 56 7 9 15 22 31 43 69 72 Xóa khóa 72 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  45. 45  Cho B-cây bậc 5: 12 29 56 7 9 15 22 31 43 69 Ít khóa -> Nhập node Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  46. 46  Cho B-cây bậc 5: 12 29 7 9 15 22 31 43 56 69 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  47. 47  Cho B-cây bậc 5: 12 29 7 9 15 22 31 43 56 69 Xóa khóa 22 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  48. 48  Cho B-cây bậc 5: 12 29 7 9 15 31 43 56 69 Mượn khóa Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  49. 49  Cho B-cây bậc 5: 12 31 7 9 15 29 43 56 69 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  50. 50  Thêm vào các khóa sau trên B-cây bậc 5 đã tạo (gồm các khóa 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56):  2, 6,12  Sau đó, xóa bỏ các khóa sau:  4, 5, 7, 3, 14 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  51. 51  Cho B-cây bậc 5: 16 3 8 28 48 1 2 5 7 12 14 25 26 29 45 52 53 Xóa khóa 8 Nhập 2 node con của 8 lại Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  52. 52  Cho B-cây bậc 5: 16 3 28 48 1 2 5 7 12 14 25 26 29 45 52 53 Nhận xét? Node 3 bị thiếu khóa → Cân bằng lại cây theo TH3 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  53. 53  Cho B-cây bậc 5: tạo node mới → hạ độ cao cây 3 16 28 48 1 2 5 7 12 14 25 26 29 45 52 53 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  54. 54  B-cây là dạng cây cân bằng, phù hợp với việc lưu trữ trên đĩa.  B-cây tiêu tốn số phép truy xuất đĩa tối thiểu cho các thao tác.  Có thể quản lý số phần tử rất lớn. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  55. 55  Xây dựng cấu trúc chỉ mục trong các hệ quản trị cơ sở dữ liệu Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  56. 56 B+ Tree Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  57. 57  Thỏa tính chất của B-Cây.  Cấu trúc của node lá và node trong có điểm khác nhau:  Thông tin chỉ mục chứa ở các node trong (không phải là node lá).  Con trỏ đến vùng dữ liệu của các khóa CHỈ được chứa ở node lá.  Giữa các node lá thường có các liên kết qua lại (giống danh sách liên kết) Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  58. 58 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  59. 59 Perryridge Mianus Redwood Brighton Downtown Mianus Redwood Round Hill Perryridge Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  60. 60  Thao tác thêm, xóa phần tử:  Thực hiện gần giống B-cây.  Lưu ý: các khóa nằm ở cây con phải có thể có giá trị lớn hơn hoặc bằng khóa trên node cha tương ứng. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  61. 61 Tập tin chỉ mục của hệ quản trị cơ sở dữ liệu FoxPro Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  62. 62  Tập tin định dạng .IDX của hệ quản trị cơ sở dữ liệu Foxpro.  Lưu trữ chỉ mục cho dữ liệu sử dụng cấu trúc cây B+.  Tham khảo: Index File Structrue (.idx) trong MSDN Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  63. 63  Gồm 2 phần chính: Header file  Header (512 byte)  Dữ liệu: tập hợp các Node 1 node của cây B+ Node 2  Kích thước:  Header: 512 byte  Node: 512 byte Node N Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  64. 64 00 – 03 Pointer to the root node Header file 04 – 07 Pointer to the free node list ( -1 if not (512 byte) present) 08 – 11 Pointer to the end of file (file size) Node 1 12 – 13 Length of key 14 Index options (any of the following Node 2 numeric values or their sums): 1 – a unique index 8 – index has FOR clause 15 Index signature (for future use) 16 – 235 Key expression (uncompiled; up to 220 characters) Node N 236 – 455 FOR expression (uncompiled; up to 220 characters ending with a null value byte) 456 – 511 Unused Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  65. 65 00 – 01 Node attributes (any of the following Header file numeric values or their sums): (512 byte) 0 – index node; 1 – root node; 2 – leaf node Node 1 02 – 03 Number of keys present (0, 1 or many) 04 – 07 Pointer to the node directly to left of the current node (on same level; -1 if not) Node 2 08 – 11 Pointer to the node directly to right of the current node (on same level; -1 if not) 12 – 511 Up to 500 characters containing the key value for the length of the key with a four- byte hexadecimal number stored in normal left-to-right format: Node N If the node is a leaf (attribute = 02 or 03) then the four bytes contain an actual table number in hexadecimal format; otherwise, Cấu trúc dữ liệu và giải thuật – HCMUS 2010 the 4 bytes contain an intra-index pointer.
  66. 66 Phần tử chỉ mục của node Cấu trúc cây B+ của tập tin IDX Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  67. 67 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  68. 68 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  69. 69 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  70. 70 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  71. 71  Các khuyết điểm lớn với cách lưu trữ trên tập tin tuần tự:  Tốc độ tìm kiếm chậm  Không an toàn  Không có nhiều tiêu chí tìm kiếm khác nhau Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  72. 72  Chỉ mục:  Là một tập hợp các phần tử chỉ mục (Index entry)  Được tổ chức theo một qui tắc xác định nhằm tăng tốc độ tìm kiếm trên bảng dữ liệu  Phần tử chỉ mục: là cấu trúc gồm tối thiểu 2 thuộc tính:  Khóa tìm kiếm: một (hay nhiều) thuộc tính, được dùng để tìm kiếm các mẫu tin trong bảng dữ liệu  Tham chiếu: con trỏ tham chiếu đến vị trí mẫu tin tương ứng với Khóa tìm kiếm Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  73. 73  Kích thước nhỏ hơn nhiều so với bảng dữ liệu  Thực hiện tìm kiếm nhanh  Cho phép ‘nhìn’ dữ liệu ở nhiều góc độ khác nhau. (Tìm kiếm trên nhiều khóa tìm kiếm khác nhau) Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  74. 74 Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  75. 75  Chỉ mục dày đặc (Dense index):  Các phần tử chỉ mục được tạo riêng cho mỗi khóa tìm kiếm  Trong trường hợp trùng khóa, tham chiếu sẽ trỏ đến bản ghi đầu tiên  Chỉ mục thưa (Sparse index)  Tạo phần tử chỉ mục cho một nhóm các khóa tìm kiếm.  Sử dụng trong trường hợp khóa tìm kiếm đã được sắp xếp Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  76. 76 An Dương Vương 1 Cách Mạng Tháng 8 2 An Dương Vương 217 Nguyễn Văn A Nguyễn Văn Cừ 4 Cách Mạng Tháng 8 101 Trần Thị B Phan Xích Long 7 Cách Mạng Tháng 8 110 Hoàng Ngọc M Trần Phú 8 Nguyễn Văn Cừ 215 Lý Minh K Xô Viết Nghệ Tĩnh 10 Nguyễn Văn Cừ 423 Vũ Quốc C Nguyễn Văn Cừ 192 Lê Nguyễn U Phan Xích Long 218 Quách P Trần Phú 222 Trần Đăng O Trần Phú 305 Phan Quỳnh L Xô Viết Nghệ Tĩnh 1234 Đặng Thị G Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  77. 77 An Dương Vương 1 Nguyễn Văn Cừ 4 An Dương Vương 217 Nguyễn Văn A Phan Xích Long 7 Cách Mạng Tháng 8 101 Trần Thị B Cách Mạng Tháng 8 110 Hoàng Ngọc M Nguyễn Văn Cừ 215 Lý Minh K Nguyễn Văn Cừ 423 Vũ Quốc C Nguyễn Văn Cừ 192 Lê Nguyễn U Phan Xích Long 218 Quách P Trần Phú 222 Trần Đăng O Trần Phú 305 Phan Quỳnh L Xô Viết Nghệ Tĩnh 1234 Đặng Thị G Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  78. 78  Về cơ bản, chỉ mục dày đặc cho kết quả tìm kiếm nhanh hơn chỉ mục thưa.  Chỉ mục thưa sử dụng ít không gian lưu trữ hơn. ->Kết hợp giữa chỉ mục dày và chỉ mục thưa: chỉ mục nhiều tầng. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  79. 79  Vấn đề:  Ngay cả khi sử dụng chỉ mục thưa, tập tin chỉ mục cũng có thể có kích thước lớn. ◼ Giả sử: dữ liệu có 100.000 bản ghi. ◼ Đánh chỉ mục thưa cho từng khối 10 bản ghi Tổng cộng có 10.000 phần tử chỉ mục  Nếu kích thước chỉ mục không nằm thể nằm trọn trong bộ nhớ trong => tốn chi phí cho việc đọc tập tin. (Khoảng 14 lần cho dữ liệu 10.000 phần tử chỉ mục) Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  80. 80  Mục tiêu:  Giảm thiểu số lần truy cập bộ nhớ phụ  Giải pháp:  Tạo chỉ mục chính cho dữ liệu (lưu trên bộ nhớ phụ)  Tạo chỉ mục thưa trên chỉ mục chính vừa tạo.  Chỉ mục thưa sẽ lưu trữ trên bộ nhớ chính.  Nếu kích thước của chỉ mục thưa lớn thì có thể tạo thêm chỉ mục thưa trên đấy. Cấu trúc dữ liệu và giải thuật – HCMUS 2010
  81. 81 Chỉ mục thưa tầng 1 Chỉ mục thưa tầng 2 Cấu trúc dữ liệu và giải thuật – HCMUS 2010 Chỉ mục chính