Indexes and how they work

Để bắt đầu bài học về index, chúng ta hãy xem một câu chuyện sau:

Tìm xe trong bãi giữ xe Có lẽ bạn cũng một lần nào đó khi giữ xe trong bãi mà quên mất mình đã gửi ở chỗ nào, và sau đó dùng cả tuổi thanh xuân để đi tìm.

Tôi lạc xe giữa đám đông

Các bạn hãy nhìn kỹ vào tấm ảnh này, bạn có thấy gì không đó chính là chìa khóa giúp chúng ta tìm xe dễ hơn đấy. Đúng rồi đó chính là B6, với việc nhớ cái số này chúng ta sẽ dễ dàng tìm được vị trí xe của mình. Người ta đã vận dụng việc đánh dấu vị trí với các số theo thứ tự để dễ dàng tìm kiếm vị trí. Chúng ta có thể thấy điều này ở trong khuôn viên trường học, người ta đánh số các dãy phòng A, B, C theo thứ tự, trừ một vài trường chẳng hạn như Nông Lâm đặt tên dãy theo loài hoa, loài cây.

Đây chính là một ví dụ về sự sắp xếp và đánh dấu trong việc tìm kiếm, index cũng hoạt động theo cách tương tư đó. Như vậy là chúng ta đã hiểu phần nào về index rồi nhá.

1. Index là gì ?

Indexing is the way to get an unordered table into an order that will maximize the query’s efficiency while searching.

Lấy một ví dụ để dễ hiểu như sau: cho một bảng Nhân Viên(ID, name)

ID	Name	Age
10	Nguyễn Văn Hoàng	17
19	Trần Đại Hùng	18
17	Dần Dần	21
16	Hoa Tiêu	23
18	Hỏa Han	21
12	Hao Tấn	18
11	Bùi Viện	19

Người ta yêu cầu chúng ta tìm tên của bạn nhân viên có Age = 18 .

Như vậy để tìm Age = 18 thì chúng ta sẽ phải đi so sánh từ trên xuống dưới tức là duyệt hết bảng để tìm ra bạn có tuổi bẳng 18. Chi phí tìm kiếm sẽ rất lớn do đó chúng ta cần một cách khác để tìm kiếm dễ dàng hơn.

2. Cách hoạt động của index?

Đầu tiên t phải cần có bộ nhớ để lưu bảng nhân viên theo trường age dưới dạng cây nhị phân.

Sau đó dựa vào thuật toán cây nhị phân để tìm ra age theo yêu cầu.

2.1 Clustered (nhóm lại)

2.2 Nonclustered (không nhóm)