Database index hoạt động như thế nào

Chắc hẳn các bạn đã khá quen thuộc với khái niệm index trong database, tuy nhiên về cách thức họat động của nó thế nào có thể bạn vẫn còn một chút mơ hồ. Hôm nay tôi sẽ cùng các bạn đi tìm hiểu xem database index hoạt động như thế nào nhé.

Đầu tiên nhắc lại một chút nhé.

Tại sao chúng ta cần đánh index?

Khi database được lưu trữ trên các ổ đĩa thiết bị, nó được lưu trữ dưới dạng khối dữ liệu(blocks of data.). Các khối ổ đĩa được cấu trúc giống như cách cấu trúc link list; bao gồm cả section data và thành phần con trỏ (pointer) đến node tiếp theo, và cả hai thành phần không cần phải được lưu trữ liên tục. Do thực tế các records chỉ có thể được sắp xếp theo một field, chúng ta có thể nói rằng tìm kiếm trên một trường không được sắp xếp bằng Linear Search phải mất N/2 block access (tính trung bình), với N là số block của table. Nếu một trường không có key (không yêu cầu tính uniques), thì phải mất tới N lượt block access. Trong khi dữ liệu được sắp xếp, chúng ta có thể search bằng Binary Search chỉ với log2(N) lượt block access. Nhưng cũng vì dữ liệu sắp xếp theo field không phải là key, nên chúng ta không cần phải tìm kiếm các giá trị trùng lặp nếu các giá trị thỏa mãn cao hơn được tìm thấy. Như vậy, hiệu suất sẽ được tăng đáng kể.

Indexing là gì?

indexing là cách sắp xếp các record trên nhiều fields. Tạo index trên một field của một table là việc tạo ra một cấu trúc dữ liệu khác giữ field value, và trỏ tới record mà nó liên quan tới. Index đó sẽ được sắp xếp, và cho phép Binary Search thực hiện. Nhược điểm của các index này là yêu cầu thêm không gian bộ nhớ, vì các index được lưu trữ cùng nhau trên một table sử dụng MyISAM engine, file này có thể nhanh chóng đạt đến kích thước giới hạn của hệ thống file underlying, nếu có quá nhiều fields của cùng một table được đánh index.

Indexing hoạt động như thế nào?

Đầu tiên chúng ta lấy một ví dụ về table:

Bây giờ ta giả sử có các trường hợp để tính toán chi phí và cách họạt động của indexing nhé. Ví dụ 1: sorted vs unsorted fields Có một table với 5,000,000 records, với size được fixed là R = 204 bytes, và được lưu trữ trong table sử dụng MyISAM engine, nó có block size mặc định là B = 1024 bytes. Do đó, số lượng factor của table trong một block sẽ là bfr = (B/R) = 1024/204 = 5 (record/disk block).
Số lượng blocks require sẽ là: N = (r/bfr) = 5000000/5 = 1,000,000 blocks. Nếu dùng Linear Search thì số lượt duyệt trung bình sẽ là N/2 = 500, 000 blocks để truy cập tìm giá trị, nhận id của field là một key field. Nhưng từ khi id được sắp xếp, Binaray Search có thể thực hiện trung bình với log2 1,000,000 = 19,93 ~ 20 lượt truy cập block. Một sự cải thiện rất lớn. Bây giờ trường firstName không được sắp xếp và cũng không phải là một key field, nhưng có thể dùng binary search, mặc dù không phải là giá trị unique, và do đó, table sẽ truy cập đến tất cả các block với số lượt N = 1,000,000. Đây là tình huống mà indexing mà mục đích chính xác.

Cho rằng một index record chỉ chứa field được đánh indexed và một pointer trỏ đến bản ghi gốc(original record), đó là lí do mà nó nhỏ hơn so với multi-field được nó trỏ đến. Vì vậy index của chính nó yêu cầu ít disk blocks hơn so với table ban đầu(original table), do đó đòi hỏi ít truy cập blocks hơn. Schema cho index của trường firstName được nêu dưới đây:

Note: pointers trong MySQL có thể là 2,3,4, or 5 bytes tùy theo size của table.

Ví dụ 2: indexing Giả sử có table có số records r = 5,000,000 với index record R = 54 bytes và sử dụng block mặc định size B = 1,024 bytes. Blocking factỏ của index sẽ là bfr = (B/R) = 1024/54 = 18 records per disk block. Tổng số blocks yêu cầu của index là N = (r/bfr) = 5000000/18 = 277,778 blocks. Bây giờ search sử dụng trường firstName có thể sử dụng index để tăng performance. Điều đó cho phép binary search của index với trung bình là log2 277,778 = 18.08 = 19 block accesses. Để tìm địa chỉ của record thực tế, mà đòi hỏi thêm một block access để đọc, nâng tổng số lên là 19 + 1 = 20 block accesses - khác xa so với 1,000,000 block acesses yêu cầu để tìm trường firstName match trong trường hợp table không đánh index(non-indexed table).

Khi nào nên sử dụng indexed?

Cái gì cũng có cái giá của nó. Đúng vậy, để tìm kiếm nhanh hơn thì chúng ta phải chấp nhận bỏ ra chi phí, ở đây tôi đang nói đến không gian bộ nhớ cần thêm. Giả sử, ta tạo một index yêu cầu thêm không gian bộ nhớ (bởi vì 277,778 blocks tăng thêm ở ví dụ bên trên, khoảng 28%), và nếu có quá nhiều indexes có thể là nguyên nhân gây ra các vấn đề tăng giới hạn kích thước file, do đó phải suy nghĩ cẩn thận chỉ dùng index cho những trường cần thiết. Vì indexes chỉ dùng để tăng tốc search cho các trường phù hợp với các records, nó có nghĩa là indexing chỉ cho output đơn giản, và trong thời gian xử lý, các hoạt động như insert hay delete nên được tránh. Cũng vì tính chất tự nhiên của binary search, tính cardinality hoặc tính uniqueness(duy nhất) của data là rất quan trọng (trong SQL, cardinality có ý nghĩa là số lượng các giá trị có thể có của một cột của table, ví dụ: cột Gender có hai giá trị có thể xuất hiện là Male và Female thì ta nói cột Gender có cardinality là 2). Indexing trên một trường với một cardinality là 2 sẽ phân chia data thành một nửa, còn khi cardinality là 1,000 thì nó sẽ trả về khoảng 1,000 records. Với cardinality thấp như vậy thì hiệu quả sẽ giảm xuống trở thành linear sort, và tối ưu query sẽ tránh sử dụng các index nếu cardinality ít hơn 30% số record, làm cho index trở thành sự lãng phí không gian bộ nhớ.

Tóm tắt sơ lược

Trên đây tôi có đề cập sơ qua về cách thức hoạt động của indexing, cùng một số ví dụ trong các trường hợp ta đánh index cho các trường trong một bảng. Các bạn cũng nên cân nhắc cẩn thận khi đánh index cho một trường nào đó, tránh gây lãng phí. Các bạn có thể tham khảo thêm về sự hoạt động của indexing tại How do database indexes work? Have fun!