date
Aug 19, 2024
slug
index-vi-du
status
Published
tags
Backend
summary
Ví dụ thực tế của index
type
Post
I. Bài toán thực tế
Lấy ví dụ tình huống sau.
Anh quản lý và đôi chân sưng tấy
Anh A mới được bổ nhiệm làm quản lý 100 giường bệnh của một bệnh viện. Mỗi bệnh nhân nằm ở một phòng riêng biệt, phân biệt các bệnh nhân bằng mã bệnh nhân. Nhiệm vụ của A là quản lý danh sách bệnh nhân ở các phòng và hỗ trợ bác sĩ thăm khám.
Tìm kiếm bệnh nhân - Cuộc sống không có index
Trong ngày, các bác sĩ sẽ đến khám riêng cho từng bênh nhân hoặc một nhóm bệnh nhân. Bác sĩ cho A một danh sách các mã bệnh nhân và yêu cầu A cho họ biết các bệnh nhân này ở phòng nào. A đi hết 100 phòng, hỏi từng bệnh nhân, đối chiếu với mã bệnh nhân của bác sĩ để lấy được danh sách hoàn chỉnh. Hơi vất vả nhưng A vẫn hài long với công việc hiện tại. Bắp chân A to lên, rắn chắc, A thầm cảm ơn những ngày làm việc vất vả chạy qua chạy lại 100 phòng đến hơn chục lượt.
Index - cuốn sổ cái
Nhưng một ngày A bệnh, A lết mãi mới được nửa vòng, A quyết định lần này là lần cuối, A đi hết 100 phòng, mỗi phòng A dừng lại và mapping thông tin bệnh nhân và số phòng vào một cuốn sổ cái. Những lần tiếp theo, khi có yêu cầu, A chỉ cần giở cuốn sổ ra và trích ra danh sách phòng của từng bệnh nhân theo yêu cầu của bác sĩ. Khi có bệnh nhân xuất viện hoặc nhập viện, A cập nhật lại trên cuốn sổ của mình, đảm bảo rằng thông tin trong cuốn sổ luôn chính xác.
Chỉ với một cuốn sổ nhỏ và một chút tỉ mỉ, công việc quản lý của A đã nhàn đi nhiều.
Rảnh rang được một thời gian, A được cất nhắc lên tuyến trên quản lý 10.000 giường bệnh. Rút kinh nghiệm, A chấp nhận đau một lần rồi thôi, A cũng lại đi thống kê toàn bộ vào cuốn sổ cái của mình, nhưng cuốn sổ của A chằng chịt toàn chữ, dày lên trông thấy. Mỗi lần bác sĩ đến khám, A dò 10.000 dòng trong cuốn sổ cái của mình. Chân A không còn đau nhưng mắt A bắt đầu nhoè dần sau 1 tuần làm việc.
Chia để trị
A thử chia cuốn sổ cái của mình thành 1.000 cuốn sổ nhỏ, mỗi cuốn 100 dòng, rồi chia theo dạng cây cân bằng vào giá sách có nhiều ngăn.
Các ngăn lớn ngoài cùng dán nhãn mã từ 1 -> 10.000, rồi tiếp tục từ 10.001 -> 20.000, tổng cộng có 10 ngăn. Trong mỗi ngăn lớn lại chia thành 10 ngăn nhỏ, mã từ 1 -> 1.000, 1.001 -> 2.000, như vậy một ngăn chỉ còn có 10 cuốn sổ nhỏ mỗi cuốn 100 bệnh nhân.
Giả sử cần tìm bệnh nhân mã số = 1.890
- Ở ngăn lớn ngoài cùng, A so sánh 1 < 1.890 < 10.000, do đó A biết cần tìm trong ngăn này
- A tìm trong ngăn 1 -> 1.000, không thấy. Chuyển sang tìm trong ngăn có giá trị > 1.000, phát hiện ngăn con thoả mãn 1001 < 1890 < 2000.
- Ngăn trong cùng này có 10 cuốn mỗi cuốn 1.000 dòng, cuốn sổ cái thứ 9 lưu mã từ 1.801 -> 1.900 sẽ là cuốn sổ mà A cần tìm.
Chỉ cần 3 bước tìm kiếm, A tìm ra được phòng bệnh nhân mong muốn. Cuốn sổ cái trong ví dụ trên tương tự với khái niệm index trong các hệ cơ sở dữ liệu. Sử dụng một vùng nhớ nhỏ để lưu giá trị của column có tính đại diên, từ đó lấy được record tương ứng.
