Tìm hiểu về chỉ mục (Index) trong hệ quản trị cơ sở dữ liệu (DBMS)

I. Giới thiệu tổng quan về Index trong các hệ quản trị cơ sở dữ liệu

1. Cấu trúc lưu trữ của bản ghi (Record)

Tất cả các bản ghi (record) của một bảng dữ liệu được tổ chức trong một file. File dữ liệu được quản lý bởi hệ quản trị cơ sở dữ liệu chứ không phải bởi hệ điều hành. Việc lưu trữ đảm bảo tính an toàn dữ liệu, tránh các trường hợp lỗi của phần cứng hay phần mềm trên hệ thống làm ảnh hưởng tới dữ liệu. Mỗi khi có một yêu cầu truy vấn dữ liệu thì hệ quản trị cơ sở dữ liệu (DBMS) sẽ xác định và trả về những dòng của các bảng quan hệ đáp ứng được câu truy vấn của người dùng. Cách thức xử lý yêu cầu phụ thuộc vào cách tổ chức lưu trữ các record trong các file này. Nếu những record được tổ chức thành những phần nhỏ và được sắp xếp theo thứ tự thì nó gần giống như một heap. Còn nếu những record được sắp xếp theo thứ tự của một vài thuộc tính thì sau đó cấu trúc file này được gọi là “đã sắp xếp”.
Để truy xuất tới những dòng dữ liệu trong một file mà được tổ chức theo heap thì đa số các hệ quản trị có thể dùng một phương pháp là scan qua tất cả các “trang đĩa” nơi mà những record được lưu trữ. Mặt khác khi tất cả các record đã được sắp xếp trong file thì có thể sử dụng phương pháp tìm nhị phân trên những trang của đĩa nới chứa các record để lấy ra các bản ghi sao cho phù hợp với yêu cầu của người dùng. Và cách tổ chức này cũng được dùng để duy trì trật tự được sắp xếp trong file bằng cách tìm chổ để thêm vào.
Ví dụ: có một danh sách học sinh được lưu trong một bảng, nó sẽ được lưu thành một file và giả sử file này sắp xếp theo thứ tự (last name - tên). Khi truy vấn dựa vào tên thì hệ thống sẽ dùng phương pháp duyệt nhị phân để đưa ra các dữ liệu phù hợp. Nếu chúng ta duyệt theo yêu cầu là ngày tháng năm sinh thì hệ thống phải duyệt qua hết các dòng trong bảng (các trang đĩa, nơi chứa các record) để đưa về kết quả cho câu truy vấn. Cách làm này không được linh hoạt cho nên khái niệm Index trong database ra đời để giải quyết hạn chế này.

2. Khái niệm Index

Index là một đối tượng trong hệ quản trị cơ sở dữ liệu – là một cấu trúc dữ liệu được sử dụng nhằm tăng tốc độ tìm kiếm trong một table, nó giống như ‘chỉ mục’ trong thư viện giúp cho người đọc tìm kiếm sách mình cần một cách nhanh chóng và hiệu quả hay phần mục lục của mỗi cuốn sách giúp ta đến chổ cần đọc nhanh hơn.
Ví dụ:

 3. Tổng quan về Index.

Cấu trúc của một chỉ mục bao gồm ít nhất hai phần là khóa tìm kiếm và con trỏ trỏ tới mẫu tin tương ứng trong bảng dữ liệu.

Index cung cấp cho chúng ta cả 2 phương pháp truy cập ngẫu nhiên và tuần tự trên trường dữ liệu đã được sắp xếp. Index có thể được tạo ra bằng cách sử dụng một hay nhiều trường (field) trong một bảng (table). Về mặt không gian lưu trữ thì một index có kích thước nhỏ hơn nhiều so với một bảng dữ liệu, nó mở ra khả năng lưu trữ index trong bộ nhớ thay cho một bảng dữ liệu khi mà dữ liệu trong nó quá lớn.

4. Cấu trúc Index cơ bản được áp dụng trong một số hệ quản trị cơ sở dữ liệu hiện tại.
Cấu trúc của Index có thể được chia làm 2 loại: clustered và non-clustered.

a. Non-Clustered Index

Một non-clustered index là một index mà trong đó thứ tự logic của khoá không giống như thứ tự vật lý của các dòng trong bảng.
Một index kiểu non-clustered thông thường nó sẽ chứa một giá trị tham chiếu tới một khối (block) dữ liệu, khối dữ liệu này nó chứa những dòng dữ liệu (cụ thể) cho những phần tử của chỉ mục được khởi tạo. ứng với mỗi việc tìm kiếm chỉ mục trên chỉ mục dạng này một khối dữ liệu mà nó chứa dòng cần tìm kiếm thì cũng phải “lấy ra”.

b. Clusterde Index

Là một index mà trong đó thứ tự logic của các khoá cũng tương tự như thứ tự vật lý của các dòng trong bảng. (thường khi ta tạo một khoá chính thì một clustered index sẽ được tạo trên cột đó).
Mỗi khi gom dữ liệu thì nó sẽ sắp xếp lại bên trong khối dữ liệu gần giống như thứ tự của index. Bởi vậy những phép toán trên các khối dữ liệu này cũng tốt gần như là thực hiện trên index. Nói một cách chính xác những phép toán trong một hệ thống cơ sở dữ liệu (database system) là khác nhau nhưng vì những dòng dữ liệu chỉ có thể lưu ở các mức vật lý và trong một bảng dữ liệu chỉ có duy nhất một clustered index được tạo ra nên nó có thể làm tăng tốc độ truy xuất. Tuy nhiên chỉ những nơi mà dữ liệu thường xuyên chúng được sắp xếp giống hay ngược lại thứ tự của clustered index hoặc khi môt dãy các phần tử được chọn.

c. Sự khác biệt giữa clustered và non-clustered

II - Khái quát về cấu trúc BTree Index.

1. Cấu trúc B+ Tree

Trong thực tế có nhiều chỉ mục kích thước của nó là rất lớn (thực tế một table có khoảng hơn một triệu dòng là điều bình thường) nên cần phải được lưu trên các thiết bị phần cứng (thiết bị nhập xuất - HDD). Ngày nay khi mà dung lượng của các thiết bị lưu trữ tăng lên rất nhanh và giá thành rẻ nên cần 1 phương pháp truy xất nhanh trên một lượng dữ liệu lớn như vậy.
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...

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 và tối đa là m cây(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 (thường thì 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:

2. Các hoạt động bên trong.

a. Tìm kiếm 

Để truy xuất những dòng dữ liệu khi câu truy vấn của người dùng đã đưa đầy đủ những thông tin đầu vào mô tả các record mà họ muốn lấy về. Việc tìm kiếm trong B+ Tree là một quá trình đệ qui và bắt đầu với nút gốc với khóa tìm kiếm là k. Quá trình tìm kiếm duyệt qua các bước.
• Thực hiện phương pháp tìm kiếm nhị phân ở trên node hiện tại, tìm kiếm với giá trị của khóa cần tìm kiếm trong một node đã được sắp xếp trước và bắt đầu với node gốc (ki < k < k(i+1))
• Nếu nút hiện tại không phải là nút lá thì đi xuống nhánh con có quan hệ với khóa ki và load node này lên để tiếp tục tìm kiếm, lặp lại quá trình này tới khi đi tới nút lá.
• nếu node là lá thì:
       o Nếu ki == k thì có có thể kết luận là record này tồn tại trong bảng dữ liệu chúng ta truy xuất vào vị trí của record đó dựa vào khóa k và đọc lên trả về cho người dùng.
       o Nếu ki != k thì có thể kết luận là record này không có.

b. Thêm

Quá trình thêm cũng tương tự như quá trình thêm vào các cây khác (giống như các loại cây nhị phân tìm kiếm), một dòng dữ liệu mới luôn luôn thêm vào node lá, sự phức tạp bắt đầu có khi một node lá bắt đầu «tràn» và làm thay đổi chỉ số chiều cao của các node liên quan.
Các bước để thêm mới một record là:
• Thêm mới một record và có khóa của nó (khóa k)
• Thực hiện tìm kiếm với khóa k trên cây, nếu khóa chưa tồn tại thì nó sẽ được thêm mới vào. Còn nếu đã tồn tại thì thông báo là dòng dữ liệu này đã có và báo trùng.
• Gọi nút lá L là nút lá nơi mà khóa k có thể được thêm vào.
• Nếu L chưa đầy thì chỉ việc thêm phần tử chỉ mục này vào. Nó bao gồm cả giá trị tìm kiếm (k) và địa chỉ trỏ tới nơi mà dữ liệu mới được thêm vào.
• Nếu L là đầy thì Lnew gọi là node lá anh em bên phải của nó, những khóa của L cùng với những phần tử của nó và kết hợp với các giá trị của Lnew sau đó phân phối lại các giá trị của chúng. Đây còn được gọi là quá trình split một node lá.

c. Xóa 

Khi xóa một phần tử trong cây thì phải chú ý đến tính đầy đủ của một node (số phần tử trong một node phải tối thiểu có m/2-1 phần tử khóa). Sự phức tạp có khi mà chúng ta xóa đi một khóa trong một node mà nó chỉ còn số phần tử tối thiểu (m/2-1 phần tử).
Quá trình xóa đi qua các bước:
• Tìm tới khóa cần xóa chứa trong node lá L.
• Từ chỉ mục chúng ta sẽ có được vị trí của dòng cần xóa trong file, vào đó và xóa nó đi.
• Nếu L có nhiều hơn m/2-1 phần tử thì ta xóa đi khóa của record đã xóa trên cây Index đi.
• Nếu L có đúng m/2-1 phần tử thì kiếm trong node là anh em bên phải của nó xem có nhiều hơn m/2-1 phần tử không ?
     o Nếu có chúng ta sẽ mượn anh em của node L một phần tử để đảm bảo tính chất tối thiểu trong một node.
     o Nếu không nó sẽ gộp hai node này lại với nhau và cân bằng lại cây chỉ mục.

3. Lợi ích của BTree Index:

BTree Index được dùng để giúp truy vấn các câu truy vấn dạng Insert, Update, Delete. Nó áp dụng được cho những yêu cầu từ một table cho những trường có tính chất đặc biệt. Ví như chúng ta có thể lấy ra những sinh viên có số điểm tích lũy trung bình trong khoảng từ 8.0 tới 9.5 trong bảng sinh viên.
Trong BTree Index thì mỗi khóa tương ứng với một dòng của dữ liệu thực. Nó sẽ được chọn khi độ trùng lắp dữ liệu là số ít.
Chỉ mục BTree sẽ được tạo nếu chúng ta tạo một bảng và chỉ định khóa chính cho nó, thì khóa chính chính là một chỉ mục kiểu B+Tree. Hoặc khi chúng ta tạo khóa ngoại thì mặc định cái trường khóa ngoại đó cũng được sử dụng BTree Index.

III - BitmapIndex

1. Giới thiệu

Trong một hệ quản trị cơ sở dữ liệu, các chỉ mục được tạo ra nhằm để xác định một cách nhanh chóng các dòng dữ liệu cần truy vấn nó nằm ở vị trí nào trên file, Bitmap Index cũng không ngoại lệ tuy nhiên các chiến lược để đánh chỉ mục Bitmap nó rất khác với các chiến lược đánh chỉ mục B+Tree.
Đây là một index nó sử dụng một cấu trúc dữ liệu đặc biệt là Bitmap. Nó được dùng để làm việc với những trường có dữ liệu rời rạc, với số lượng ít các giá trị khác nhau (tức mức độ lặp lại ở trong trường này thường là lớn), nhưng tần suất truy vấn đến trường này là rất cao. Ví dụ như trường giới tính (Gender), trường này chỉ bao gồm hai giá trị là Nam hoặc Nữ. Hình ảnh Bitmap Index cho ví dụ trên như sau:

Ở cột Indentifier đề cập tới môt số, số này là một số duy nhất dùng để nhận biết các hàng khác nhau. Giới tính là dữ liệu sẽ đánh chỉ mục nội dung của Bitmap được hiển thị như là 2 cột của Bitmap.
Phần Bitmap để tối ưu khả năng lưu trữ người ta thường dùng phương pháp nén dữ liệu, đa số là dùng các thuật toán nén tốt trên các trường dữ liệu có độ trùng lắp thông tin lớn như là RLE (Run length Encoding).

2. Cấu trúc 

Một Bitmap Index cũng được tổ chức như là B-Tree Index, nhưng phần lá của mỗi node lưu một dãy các bit cho mỗi khoá thay vì danh sách các ROWID (mã phân biệt của từng dòng). Mỗi bit trong danh sách Bitmap đó tương ứng với một ROWID, và nếu giá trị bit đó được khởi tạo, điều đó có nghĩa là hàng có ROWID tương ứng sẽ chứa giá trị khoá

3. Sử dụng Bitmap Index

Bitmap Index được sử dụng khi:
a. Mức độ dữ liệu trùng lắp không lớn.
Ví dụ trong Oracle thì quyết định là: distinct val/ total val < 1% thì dùng Bitmap Index : Tức nếu số giá trị rời rạc của một cột trong bảng trên tổng số dòng của bảng mà nhỏ hơn 1% thì ta dùng Bitmap Index.Ví dụ trường giới tính: distinct val = 2 <số giá trị riêng biệt> và Total val = 1000 dòng. 2/1000 < 10% --> dùng Bitmap.
Hoặc nếu trong một cột mà có mức độ lặp lại của một giá trị nào đó hơn 100 lần thì ta dùng Bitmap Index.

b. Không hoặc là ít thao tác update hoặc insert lên bảng dữ liệu.
Vì cách tổ chức của Bitmap khá phức tạp nên việc update lại thông tin của Bitmap Index phải trả một chi phí lớn cho việc duy trì cấu trúc của nó. Nó chiếm nhiều thời gian, không gian ổ cứng và thiết bị nhập xuất. Người thiết kế phải đảm bảo rằng không để vượt quá phạm vi kích thước của chỉ mục.
Việc sử dụng các phương pháp để hạn chế chi phí trên các chỉ mục không bị gián đoạn khi các thao tác insert, delete, update của index nó không bị giới hạn tài nguyên.

c. Khi mà có nhiều cột.
Một trong những lợi thế lớn nhất của Bitmap Index là có thể có nhiều cột trong đó nên nó có thể kết hợp các cột dữ liệu lại với nhau.
Trong trường hợp có một bảng có thể có nhiều hơn một cột có khả năng làm index để cải thiện tốc độ quét (scan) bảng dữ liệu.

5. So sảnh Bitmap Index và Btree Index.

IV. Kết luận

Index là môt đối tượng trong cơ sở dữ liệu nó được đưa ra để làm tăng tốc độ truy vấn dữ liệu trong các hệ quản trị cơ sở dữ liệu lớn hiện nay (như Oracle, Ms. SQL server, MySql, DB2…).
Index gồm có nhiều loại nhưng chủ yếu phổ biến nhất là 2 loại BTree Index, Bitmap Index.

1. Ứng dụng
Như đã nói ở trên index được đưa ra để tăng tốc độ truy vấn dữ liệu, khi mà lượng dữ liệu trong một table là nhiều. Nhờ vào index mà khi chúng ta cần truy cập nhanh dựa trên một hay nhiều khóa nào đó nó sẽ không phải tốn chi phí scan dữ liệu, đây là chi phí rất lớn để lấy dữ liệu lên đúng với yêu cầu của người dùng.
Lưu ý rằng khi chọn một loại index để cài đặt cho một cơ sở dữ liệu thì chúng ta cần phải cân nhắc dùng cái nào. Nếu mà dùng sai nó sẽ gây tới sự phản tác dụng. Bởi vì nếu cần dùng BTree Index mà dùng Bitmap Index thì sẽ tốn không gian lưu trữ trong khi đó cũng không đáp ứng được nhu cầu truy xuất nhanh vì phải duyệt qua bảng Bitmap.

2. Hạn Chế
- Vì khi dữ liệu thêm mới cần phải cập nhật và duy trì tính chất của từng loại index nên nó làm chậm quá trình thêm mới và update dữ liệu.
- Tốn không gian lưu trữ vì phải lưu trữ thêm nó trong bộ nhớ.
- Khi cập nhật dữ liệu cần phải tốn chi phí cập nhật lại chỉ mục để truy xuất.

V. Tài liệu tham khảo

http://en.wikipedia.org/wiki/Index_(database)
http://mattfleming.com/node/192
http://www.dbasupport.com/forums/showthread.php?t=38893