Single index là gì?

Trong cơ sở dữ liệu (database), chỉ mục đơn (single index) là chỉ mục (index) dựa trên MỘT cột (column) thay vì nhiều cột như chỉ mục phức hợp (composite index).

Ví dụ chúng ta có bảng (table) users như sau:

ID | first_name | last_name    | class      | position |
------------------------------------------------------------------------------
 1 | Teemo      | Shroomer     | Specialist | Top      |
 2 | Cecil      | Heimerdinger | Specialist | Mid      |
 3 | Annie      | Hastur       | Mage       | Mid      |
 4 | Fiora      | Laurent      | Slayer     | Top      |
 5 | Garen      | Crownguard   | Fighter    | Top      |
 6 | Malcolm    | Graves       | Specialist | ADC      |
 7 | Irelia     | Lito         | Figher     | Top      |
 8 | Janna      | Windforce    | Controller | Support  |
 9 | Jarvan     | Lightshield  | Figher     | Top      |
10 | Katarina   | DuCouteau    | Assassin   | Mid      |
11 | Kayle      | Hex          | Specialist | Top      |
12 | Emilia     | LeBlanc      | Mage       | Mid      |
13 | Lee        | Sin          | Fighter    | Jungle   |
14 | Lux        | Crownguard   | Mage       | Mid      |
15 | Sarah      | Fortune      | Marksman   | ADC      |
16 | Morgana    | Hex          | Controller | Support  |
17 | Orianna    | Reveck       | Mage       | Mid      |
18 | Sona       | Buvelle      | Controller | Support  |
19 | Jericho    | Swain        | Mage       | Mid      |
20 | Shauna     | Vayne        | Marksman   | ADC      |
21 | Xin        | Zhao         | Fighter    | Jungle   |
22 | Yorick     | Mori         | Tank       | Top      |
23 | Wu         | Kong         | Fighter    | Jungle   |

Nếu chúng tôi tạo chỉ mục đơn (single index) trên cột first_name:

CREATE INDEX first_name_index ON users (first_name) USING BTREE;

Sẽ tạo một chỉ mục đơn (single index), được sắp xếp theo first_name với một con trỏ (pointer) trỏ đến khóa chính (primary key), giống như:

Annie    -> 3
Cecil    -> 2
Emilia   -> 12
Fiora    -> 4
Garen    -> 5
Irelia   -> 7
Janna    -> 8
Jarvan   -> 9
Jericho  -> 19
Katarina -> 10
Kayle    -> 11
Lee      -> 13
Lux      -> 14
Malcolm  -> 6
Morgana  -> 16
Orianna  -> 17
Sarah    -> 15
Shauna   -> 20
Sona     -> 18
Teemo    -> 1
Wu       -> 23
Xin      -> 21
Yorick   -> 22

Sau đó, một truy vấn (query) như:

SELECT * FROM users WHERE first_name = 'Teemo';

sẽ chỉ mất O (log_2 (n)) lần đọc vì cơ sở dữ liệu có thể thực hiện tìm kiếm nhị phân (binary search) trên chỉ mục này, vì nó được sắp xếp theo first_name.