Tổng quan về giáo trình

Giáo trình bài giảng Cấu Trúc Chỉ Mục Trong Hệ Quản Trị Cơ Sở Dữ Liệu (thuộc học phần Database Management Systems - Mã môn học: CO3021) được biên soạn bởi TS. Võ Thị Ngọc Châu thuộc Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – ĐHQG-HCM (Ho Chi Minh City University of Technology), áp dụng cho chương trình đào tạo ngành Khoa học Máy tính trong Học kỳ 1 năm học 2020–2021.

Trong chương trình đào tạo kỹ sư và cử nhân ngành Công nghệ Thông tin/Khoa học Máy tính, môn học Hệ Quản trị Cơ sở Dữ liệu giữ vị trí khối kiến thức cơ sở ngành cốt lõi, cung cấp các nguyên lý nền tảng về tổ chức lưu trữ vật lý, quản trị dữ liệu và cơ chế xử lý nội tại của các hệ quản trị cơ sở dữ liệu quan hệ (RDBMS).

Mục tiêu học tập của học phần hướng tới việc trang bị cho người học:

  • Khả năng hiểu rõ cấu trúc tệp dữ liệu trên đĩa từ (disk storage) và các đường truy cập phụ trợ (auxiliary access structures).
  • Kỹ năng phân tích định lượng chi phí truy xuất đĩa (block accesses/IO cost) giữa các chiến lược quét tuyến tính (linear search), tìm kiếm nhị phân (binary search) và tìm kiếm qua chỉ mục (index search).
  • Nắm vững nguyên lý hoạt động, cấu trúc bản ghi và giải thuật của các loại chỉ mục một cấp (Single-level Ordered Indexes: Primary, Clustering, Secondary) và chỉ mục đa cấp động (Dynamic Multilevel Indexes: B-Trees, B+-Trees).

Phương pháp tiếp cận của tài liệu đi từ mô hình toán học định lượng về dung lượng khối (block size), hệ số khối (blocking factor) đến mô phỏng chi tiết các bước tra cứu dữ liệu. Điểm đặc trưng của tài liệu là gắn liền cơ sở lý thuyết chuẩn hóa quốc tế với các bài toán tính toán chi phí cụ thể, làm rõ mối liên hệ giữa tổ chức vật lý của tệp bản ghi và hiệu năng xử lý truy vấn.

Nội dung kiến thức cốt lõi

Các chương và chủ đề chính

Đề cương môn học Database Management Systems (CO3021) được cấu trúc thành 7 chương chính theo tiến trình phát triển từ lưu trữ vật lý đến quản trị giao dịch:

  • Chapter 1. Overall Introduction to Database Management Systems: Tổng quan kiến trúc, thành phần và chức năng của hệ quản trị cơ sở dữ liệu.
  • Chapter 2. Disk Storage and Basic File Structures: Cơ chế lưu trữ trên đĩa cứng, cấu trúc bản ghi, khối dữ liệu và các dạng tổ chức tệp cơ bản (tệp không sắp thứ tự - Heap file, tệp có sắp thứ tự - Sequential/Ordered file, và tệp băm - Hashed file).
  • Chapter 3. Indexing Structures for Files: Cấu trúc chỉ mục cho tệp dữ liệu, phân loại chỉ mục một cấp (Primary, Clustering, Secondary Indexes), chỉ mục đa cấp (Multilevel Indexes), và chỉ mục cây tìm kiếm cân bằng động (B-Trees, B+-Trees).
  • Chapter 4. Query Processing and Optimization: Các giai đoạn xử lý truy vấn và các giải thuật tối ưu hóa câu truy vấn.
  • Chapter 5. Introduction to Transaction Processing Concepts and Theory: Khái niệm cơ bản và lý thuyết về xử lý giao dịch (Transaction Processing).
  • Chapter 6. Concurrency Control Techniques: Các kỹ thuật kiểm soát tương tranh và đồng thời (Locking techniques, Timestamps).
  • Chapter 7. Database Recovery Techniques: Các giải pháp và kỹ thuật phục hồi cơ sở dữ liệu sau sự cố.

Kiến thức nền tảng được xây dựng

Nội dung trọng tâm trong Chapter 3 thiết lập các nguyên lý nền tảng về chỉ mục:

1. Khái niệm và vai trò của chỉ mục

Chỉ mục là cấu trúc truy cập phụ trợ bổ sung cho tệp dữ liệu chính (data file) đã tồn tại một cơ chế tổ chức gốc (unordered, ordered, hoặc hashed). Chỉ mục đóng vai trò là đường truy cập thứ cấp (secondary access path), cung cấp phương thức định vị bản ghi mà không làm thay đổi vị trí vật lý của các bản ghi trên đĩa, nhằm mục đích tăng tốc độ truy xuất dữ liệu theo các điều kiện tìm kiếm cụ thể. Chỉ mục được quản lý dưới dạng các tệp có thứ tự bổ sung trên đĩa.

2. Chỉ mục đơn cấp (Single-level Ordered Indexes)

Tệp chỉ mục bao gồm nhiều phần tử (entries), mỗi phần tử là một cặp <Field value, Pointer(s)>. Trường dữ liệu làm căn cứ đánh chỉ mục gọi là trường chỉ mục (indexing field) và có thể sắp thứ tự được. Con trỏ có thể là con trỏ khối (block pointer) hoặc con trỏ bản ghi (record pointer). Phân loại chỉ mục gồm:

Loại chỉ mục Trường đánh chỉ mục Tệp dữ liệu chính Đặc tính phân loại Số lượng mục chỉ mục ($r_i$)
Primary Index Khóa chính có sắp thứ tự (Ordering key) Tệp có sắp thứ tự (Ordered file) Chỉ mục thưa (Non-dense / Sparse) Bằng số khối của tệp dữ liệu ($b$)
Clustering Index Trường phi khóa có sắp thứ tự (Ordering non-key) Tệp có sắp thứ tự (Ordered file) Chỉ mục thưa (Non-dense / Sparse) Bằng số giá trị phân biệt của trường chỉ mục
Secondary Index (Key) Trường khóa không sắp thứ tự (Non-ordering key) Tệp bất kỳ (Ordered / Unordered) Chỉ mục đặc (Dense) Bằng số bản ghi của tệp dữ liệu ($r$)
Secondary Index (Non-key) Trường phi khóa không sắp thứ tự (Non-ordering non-key) Tệp bất kỳ (Ordered / Unordered) Chỉ mục đặc (Dense / Indirection) Tùy thuộc phương án triển khai (1, 2, hoặc 3)

Nguyên tắc ràng buộc vật lý: Một tệp dữ liệu chỉ có tối đa một thứ tự sắp xếp vật lý, do đó chỉ có thể có tối đa một Primary Index hoặc một Clustering Index, nhưng có thể có nhiều Secondary Indexes.

3. Chỉ mục đa cấp (Multilevel Indexes)

Do tệp chỉ mục cấp một (first-level index) là một tệp có sắp thứ tự, hệ thống có thể tạo tiếp chỉ mục cấp hai (second-level index) cho chính tệp chỉ mục cấp một, và lặp lại cho đến cấp đỉnh (top level) khi toàn bộ mục chỉ mục vừa vặn trong đúng một khối đĩa.

  • Hệ số phân nhánh (Fan-out, ký hiệu $fo$): tương đương hệ số khối của chỉ mục ($fo = bfr_i$).
  • Chi phí tìm kiếm trên chỉ mục đa cấp: xấp xỉ $\lceil\log_{fo}(b_i)\rceil$ lần truy xuất khối, giảm đáng kể so với tìm kiếm nhị phân thông thường $\lceil\log_2(b_i)\rceil$.

4. Chỉ mục đa cấp động (Dynamic Multilevel Indexes: B-Trees và B+-Trees)

Để khắc phục nhược điểm về chi phí ghi đĩa lớn khi chèn/xóa trên các tệp chỉ mục sắp thứ tự tĩnh, các cấu trúc cây tìm kiếm cân bằng được sử dụng:

  • Mỗi nút tương ứng với một khối đĩa và luôn được duy trì độ lấp đầy từ 50% đến 100% (ngoại trừ nút gốc).
  • B-Tree: Con trỏ dữ liệu ($Pr_i$) được lưu trữ ở cả nút trung gian (internal nodes) lẫn nút lá (leaf nodes). Cấu trúc nút trung gian có dạng: $\langle P_1, \langle K_1, Pr_1\rangle, P_2, \langle K_2, Pr_2\rangle, \dots, \langle K_{q-1}, Pr_{q-1}\rangle, P_q\rangle$ với $q \le p$ ($p$ là bậc của cây).
  • B+-Tree: Con trỏ dữ liệu chỉ được lưu trữ tại các nút lá. Các nút trung gian chỉ chứa khóa tìm kiếm và con trỏ cây ($P_i$) để điều hướng. Các nút lá được liên kết tuần tự với nhau (linked leaf nodes), giúp tối ưu hóa truy vấn quét theo phạm vi (range queries) và giảm chiều cao của cây.

Kỹ năng phát triển

Thông qua nội dung giáo trình, người học phát triển các kỹ năng chuyên môn:

  • Kỹ năng kỹ thuật (Technical skills): Tính toán dung lượng lưu trữ của tệp chỉ mục, blocking factor ($bfr, bfr_i, bfr_{ii}$), số khối chỉ mục ($b_i$), và xác định chính xác số lượng truy xuất khối (block accesses) đối với các trường hợp truy vấn điểm (equality search) và truy vấn phạm vi.
  • Kỹ năng phân tích (Analytical skills): So sánh hiệu năng giữa các phương án đánh chỉ mục; phân tích sự đánh đổi (trade-offs) giữa tốc độ đọc truy vấn và chi phí bảo trì cấu trúc chỉ mục khi có các thao tác cập nhật (Insert/Delete).
  • Kỹ năng thực tiễn (Practical competencies): Vận dụng lý thuyết phân loại chỉ mục để thiết kế cấu trúc lưu trữ dữ liệu hiệu quả trong các hệ quản trị CSDL quan hệ thực tế.

Phương pháp giảng dạy và học tập

Giáo trình sử dụng phương pháp sư phạm diễn dịch kết hợp mô hình hóa định lượng. Mỗi loại cấu trúc chỉ mục đều đi kèm định nghĩa toán học, mô hình tổ chức khối bộ nhớ và các bài toán tính toán chi phí truy xuất đĩa dựa trên các tham số vật lý giả định.

Các ví dụ và bài tập định lượng tiêu biểu trong tài liệu

  • Ví dụ 1 (Primary Index): Tệp EMPLOYEE có $r = 30.000$ bản ghi, kích thước bản ghi $R = 150$ bytes, kích thước khối $B = 512$ bytes $\rightarrow bfr = 3$ bản ghi/khối, tổng số khối tệp dữ liệu $b = 10.000$ khối. Với chỉ mục chính trên trường SSN ($V_{SSN} = 9$ bytes, con trỏ khối $P_B = 6$ bytes $\rightarrow R_i = 15$ bytes, $bfr_i = 34$ mục/khối), số khối chỉ mục là $b_i = 295$ khối. Chi phí tìm kiếm nhị phân trên chỉ mục cộng thêm 1 lần truy xuất bản ghi là $9 + 1 = 10$ lần truy xuất khối (so với $5.000$ lần quét tuyến tính hoặc $14$ lần tìm kiếm nhị phân trên tệp dữ liệu gốc).
  • Ví dụ 2 (Clustering Index): Tệp dữ liệu có trường DEPT_NUMBER gồm 125 giá trị phân biệt. Với $V_{DEPT_NUMBER} = 4$ bytes, $P_B = 6$ bytes $\rightarrow R_i = 10$ bytes, $bfr_i = 51$ mục/khối. Số khối chỉ mục $b_i = \lceil 125 / 51 \rceil = 3$ khối. Chi phí tìm kiếm nhị phân trên chỉ mục là $\lceil\log_2 3\rceil + 1 = 2 + 1 = 3$ lần truy xuất khối.
  • Ví dụ 3 & 4 (Secondary Index): Phân tích trường hợp đánh chỉ mục trên trường khóa (chi phí $10 + 1 = 11$ lần truy xuất khối với $b_i = 883$ khối) và trường phi khóa sử dụng cấu trúc tầng gián tiếp (indirection level) với danh sách con trỏ bản ghi, tính toán chi phí lấy bản ghi đầu tiên ($2 + 1 + 1 = 4$ truy xuất) và lấy toàn bộ bản ghi trùng khớp ($2 + 4 + 240 = 246$ truy xuất khối).
  • Ví dụ 5 (Multilevel Index): Xây dựng chỉ mục đa cấp trên nền chỉ mục phụ có $b_1 = 938$ khối, hệ số phân nhánh $fo = 32 \rightarrow b_2 = \lceil 938 / 32 \rceil = 30$ khối $\rightarrow b_3 = \lceil 30 / 32 \rceil = 1$ khối (cấp đỉnh). Tổng chi phí tìm kiếm chỉ mất $3 + 1 = 4$ lần truy xuất khối.

Phương pháp đánh giá và tự học

Giáo trình định hướng người học tự đánh giá thông qua:

  • Phân tích các câu hỏi cơ chế: "Tại sao Primary Index là chỉ mục thưa?", "Vấn đề xảy ra khi chèn/xóa bản ghi trong Primary Index và Clustering Index là gì và cách giải quyết?", "Tại sao B+-Tree có số tầng ít hơn B-Tree với cùng một dung lượng dữ liệu?".
  • Rèn luyện kỹ năng vẽ và biến đổi trạng thái cây tìm kiếm bậc $p$ qua các chuỗi thao tác chèn khóa mẫu (ví dụ: chèn dãy giá trị 8, 5, 1, 7,... vào cây bậc $p = 3$).

Điểm nổi bật và tài liệu tham khảo

Tài liệu được xây dựng dựa trên sự tổng hợp từ các giáo trình chuẩn quốc tế về hệ cơ sở dữ liệu:

  1. R. Elmasri, S. B. Navathe, Fundamentals of Database Systems, 6th Edition, Pearson-Addison Wesley, 2011; và 7th Edition, Pearson, 2016. (Nguồn trích dẫn chính cho các sơ đồ cấu trúc chỉ mục Figure 17.x và các bảng phân loại Table 17.x).
  2. J. Widom, Database System Implementation, Prentice-Hall, 2000.
  3. J. Widom, Database Systems: The Complete Book, Prentice-Hall, 2002.
  4. A. Silberschatz, H. F. Korth, S. Sudarshan, Database System Concepts, 3rd Edition, McGraw-Hill, 1999.

Điểm nổi bật trong nội dung bài giảng là tính nhất quán về mặt ký hiệu và mô hình toán học:

  • Hệ thống hóa toàn diện các dạng chỉ mục đơn cấp dựa trên hai thuộc tính: tính chất của trường chỉ mục (Key vs Non-key) và cách tổ chức của tệp dữ liệu chính (Ordered vs Unordered).
  • Làm rõ sự chuyển tiếp công nghệ từ chỉ mục tĩnh kiểu ISAM (Indexed Sequential Access Method) sang các cấu trúc cây động B-Tree/B+-Tree - kiến trúc chỉ mục tiêu chuẩn đang được tích hợp trong hầu hết các DBMS hiện nay (Indexes in Today's DBMSs).

Đối tượng sử dụng giáo trình

  • Sinh viên chuyên ngành: Tài liệu phục vụ trực tiếp cho sinh viên năm thứ 2 và năm thứ 3 thuộc chương trình đào tạo ngành Khoa học Máy tính và Kỹ thuật Máy tính tại Trường Đại học Bách Khoa – ĐHQG-HCM và các trường đại học khối kỹ thuật.
  • Yêu cầu kiến thức tiên quyết (Prerequisites):
    • Cấu trúc dữ liệu và giải thuật (Data Structures & Algorithms): Nắm vững các cấu trúc mảng, danh sách liên kết, cây nhị phân, giải thuật tìm kiếm nhị phân.
    • Kiến trúc máy tính và Hệ điều hành (Computer Architecture / Operating Systems): Hiểu rõ nguyên lý lưu trữ phân cấp, cấu trúc khối đĩa (disk blocks), bộ đệm (buffer pool) và các thao tác xuất/nhập (I/O operations).
  • Giảng viên và cán bộ nghiên cứu: Tài liệu cung cấp khung bài giảng chuẩn hóa, hệ thống bài tập định lượng mẫu và hệ thống hình vẽ mô tả cấu trúc khối dữ liệu phục vụ công tác giảng dạy lý thuyết hệ quản trị cơ sở dữ liệu.
  • Người tự học và kỹ sư phần mềm: Cung cấp tài liệu tham khảo nền tảng để hiểu rõ cơ chế vật lý bên dưới của chỉ mục, hỗ trợ việc thiết kế chỉ mục và tối ưu hóa câu lệnh truy vấn trong các hệ quản trị CSDL thực tế.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với đối tượng người học nào?

Giáo trình được thiết kế cho sinh viên ngành Khoa học Máy tính, Kỹ thuật Phần mềm và Công nghệ Thông tin cần học sâu về nguyên lý hoạt động tầng thấp (database internals) của các hệ quản trị cơ sở dữ liệu.

2. Cần chuẩn bị kiến thức nền tảng nào trước khi tiếp cận tài liệu?

Người học cần nắm vững kiến thức về cấu trúc dữ liệu tuyến tính và phi tuyến (mảng, con trỏ, cây tìm kiếm), thuật toán tìm kiếm nhị phân, cùng các khái niệm cơ bản về tổ chức phần cứng máy tính như kích thước khối đĩa (disk block size) và truyền nhận dữ liệu giữa đĩa và bộ nhớ chính.

3. Sự khác nhau cơ bản giữa Primary Index, Clustering Index và Secondary Index là gì?

  • Primary Index: Định nghĩa trên trường khóa chính có sắp thứ tự của tệp dữ liệu; là chỉ mục thưa; mỗi khối tệp dữ liệu tương ứng một mục chỉ mục dựa trên bản ghi neo (block anchor).
  • Clustering Index: Định nghĩa trên trường phi khóa có sắp thứ tự của tệp dữ liệu; là chỉ mục thưa; mỗi giá trị phân biệt tương ứng một mục chỉ mục trỏ tới khối đầu tiên chứa giá trị đó hoặc cụm khối riêng biệt.
  • Secondary Index: Định nghĩa trên trường không sắp thứ tự (có thể là trường khóa hoặc phi khóa); là chỉ mục đặc; cung cấp đường truy cập phụ trợ mà không thay đổi vị trí vật lý của bản ghi.

4. Tại sao B+-Tree lại được ưu tiên sử dụng phổ biến trong các DBMS hiện đại hơn B-Tree?

Trong B+-Tree, các con trỏ trỏ tới dữ liệu thực chỉ được lưu ở các nút lá, còn các nút trung gian chỉ chứa khóa và con trỏ cây. Do đó, kích thước một mục ở nút trung gian nhỏ hơn, làm tăng hệ số phân nhánh ($fo$) và giảm số tầng của cây, từ đó giảm số lần đọc đĩa. Đồng thời, các nút lá của B+-Tree được liên kết tuần tự, cho phép thực hiện các phép quét phạm vi (range queries) hiệu quả hơn so với B-Tree.

5. Tài liệu có cung cấp phương pháp tính toán chi phí truy xuất dữ liệu không?

Có. Giáo trình cung cấp công thức chi tiết để tính: hệ số khối của dữ liệu ($bfr$), hệ số khối của chỉ mục ($bfr_i$), tổng số khối tệp dữ liệu ($b$), tổng số khối tệp chỉ mục ($b_i$), và chi phí I/O (số lần truy xuất khối) tương ứng cho từng loại chỉ mục trong các điều kiện tìm kiếm cụ thể.

Kết luận

Bài giảng Chapter 3: Indexing Structures for Files trong học phần Database Management Systems (CO3021) do TS. Võ Thị Ngọc Châu biên soạn cung cấp nền tảng lý thuyết và định lượng về các cấu trúc chỉ mục trong hệ quản trị cơ sở dữ liệu. Lộ trình học tập được thiết kế mạch lạc, đi từ cơ sở tổ chức tệp đĩa, phân tích các dạng chỉ mục đơn cấp, đến các cấu trúc chỉ mục đa cấp động B-Tree/B+-Tree. Tài liệu chuẩn hóa dựa trên các giáo trình quốc tế kinh điển của Elmasri/Navathe và Widom, đóng vai trò tài liệu học tập và tra cứu cho sinh viên và người làm việc trong lĩnh vực kỹ thuật dữ liệu.