Bài giảng Tổ chức Index hiệu quả

1Thiết kế và quản trị cơ sở dữ liệu
Vũ Tuyết Trinh 
Tổ chức Index hiệu quả
Vũ Tuyết Trinh
trinhvt-fit@mail.hut.edu.vn
Bộ môn Hệ thống thông tin, Viện CNTT&TT
Đại học Bách Khoa Hà Nội
Nội dung 
 Một sô kiểu truy vấn
 Đánh chỉ mục (mục tiêu) 
 Tổ chức index
 Tổ chức dữ liệu trên đĩa
 Chi phí cho Index (tạo, duy trì, sử dụng)
 “Phân tán” dữ liệu
2Thiết kế và quản trị cơ sở dữ liệu
Vũ Tuyết Trinh 
Một số kiểu truy vấn
 Truy vấn với điều kiện 
chính xác trên khóa
 Truy vấn với điều kiện 
trên thuộc tính bất kỳ
 Truy vấn với điều kiện 
trong khoảng
3
SELECT balance
FROM accounts
WHERE number = 1023;
SELECT balance
FROM accounts
WHERE branchnum = 100;
SELECT number
FROM accounts
WHERE balance > 10000;
SELECT *
FROM employees
WHERE name = „Jensen‟ 
and firstname = „Carl‟ 
and age < 30;
Một số kiểu truy vấn (2)
 Truy vấn lồng nhau
 Truy vấn có sắp xếp
 Truy vấn nhóm 
 Truy vấn kết nối 
SELECT *
FROM accounts
WHERE balance = ( select max(balance) 
from accounts)
SELECT *
FROM accounts
ORDER BY balance;
SELECT branchnum, avg(balance)
FROM accounts
GROUP BY branchnum;
SELECT distinct branch.adresse
FROM accounts, branch
WHERE 
accounts.branchnum = branch.number
and accounts.balance > 10000;
3Thiết kế và quản trị cơ sở dữ liệu
Vũ Tuyết Trinh 
5
Đánh chỉ mục trong CSDL
{Tuples}index
Điều kiện 
truy nhập 
dữ liệu
Bản ghi
Phù hợp
Khóa tìm kiếm
(Sequential vs. Non sequential)
B-Tree
96
75 83 107
96 98 103 107 110 12083 92 9575 80 8133 48 69
4Thiết kế và quản trị cơ sở dữ liệu
Vũ Tuyết Trinh 
Các tham số ảnh hưởng đến hiệu năng
 Số lượng các nút
 Kích thước khóa
 Độ sâu của cây
 Số trang nhớ sử dụng 
 Chi phí duy tri (thêm, cập nhật, xóa) 
Hash Index
 Hàm băm (hash function)
 (key, value) 
Hashed key values
0
1
n
R1 R5
R3 R6 R9 R14 R17 R21 R25
Hash
function
key
2341
5Thiết kế và quản trị cơ sở dữ liệu
Vũ Tuyết Trinh 
Clustered vs. Unclustered Index
Index entries
Data entries
direct search for 
(Index File)
(Data file)
Data Records
data entries
Data entries
Data Records
CLUSTERED UNCLUSTERED
Dense vs. Sparse index
P1 PiP2
record
record
record
6Thiết kế và quản trị cơ sở dữ liệu
Vũ Tuyết Trinh 
Các ràng buộc và chỉ mục
 Khóa chính, khóa duy nhất
 a non-clustered index.
 Khóa ngoài 
 Không tạo index
Phân cụm bảng dữ liệu
 Ví dụ
Supplier(supplier_ID, supplier_address)
Onorder(supplier_ID, part_ID, quantity)
 Cluster: gồm dữ liệu từ 1 hoặc nhiều bảng có
chung 1 hoặc 1 số cột
 Cluster key: cột chung giữa các bảng
 Supplier_ID
12
7Thiết kế và quản trị cơ sở dữ liệu
Vũ Tuyết Trinh 
Phân cụm bảng khi nào? 
 Truy vấn kết nối các bảng được tạo trong
cùng cụm? 
 Truy vấn dữ liệu trên từng bảng dựa trên
trường dữ liệu khóa (cluster key)?
 Đọc toàn bộ bảng ?
 Thêm bản ghi ?
 Xóa bản ghi ?