ữ ệ
ấ
ả
C u trúc d li u và gi
ậ i thu t
B-Cây
Giảng viên: Đậu Ngọc Hà Dương
Nội dung trình bày
2
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
3
Cây tìm kiếm m-nhánh
mway search tree
mway tree
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Định nghĩa
ế
ấ
Cây tìm ki m mnhánh là cây có tính ch t:
Có tối đa m-1 khóa trong mỗi node (v1, v2,.., vk) (k (cid:0)
m-1).
Các giá trị khóa trong node được tổ chức có thứ tự
(v1 < v2 < ... < vk).
Một node có k khóa thì sẽ có k + 1 cây con (các cây
con có thể rỗng).
Các cây con đặt giữa hai giá trị khóa.
Hai cây con nằm ở hai đầu của dãy khóa
Mỗi khóa sẽ có cây con trái và cây con phải.
4
Các giá trị của cây con trái sẽ nhỏ hơn giá trị của khóa.
Các giá trị của cây con phải sẽ lớn hơn giá trị của khóa.
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Ví dụ
5
16 25
10 14 20 33 42
11 28 49
ế Cây tìm ki m 3nhánh
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thao tác trên cây
Tìm ki mế
Thêm ph n tầ ử
Xóa ph n tầ ử
6
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Tìm kiếm
ợ
ị
T ng quát hóa t
ừ ườ tr
ng h p cây nh phân tìm
ổ ki mế
X là giá trị cần tìm
Nếu X < v1 thì tìm X bên nhánh trái của v1.
Ngược lại, nếu X > vk thì tìm X bên nhánh phải của
vk.
Nếu X = vi thì thông báo tìm thấy.
Nếu vi < X < vi+1 thì tìm X tại cây con nằm giữa vi và
vi+1.
7
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử
ợ
ị
T ng quát hóa t
ừ ườ tr
ng h p cây nh phân tìm
ổ ki mế
X là giá trị cần thêm vào cây.
Duyệt cây tìm X trên cây.
Nếu X đã tồn tại trên cây thì không thêm.
Nếu X chưa tồn tại (tìm thấy node rỗng) thì
Nếu node cha (của node rỗng tìm thấy) còn có thể thêm X
vào thì thêm X vào node cha.
Ngược lại, tạo node mới và thêm X vào node đó.
8
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử
9
16 25
10 14 20 33 42
11 13 28 49
Thêm vào giá tr ị 13
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử
10
16 25
10 14 20 33 42
11 28 37 49
Thêm vào giá tr ị 37
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
ươ
ự
ế
ị
T
ng t
cây nh phân tìm ki m
Tìm vị trí của phần tử X cần xóa.
Nếu X nằm giữa hai cây con rỗng thì xóa X.
Nếu X có cây con, thay thế X bằng:
Phần tử lớn nhất bên cây con trái của X hoặc
Phần tử nhỏ nhất bên cây con phải của X
11
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
12
16 25
10 14 20 33 42
11 28 49
Xóa giá tr ị 20
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
13
16 25
10 14 33 42
11 28 49
Xóa giá tr ị 25
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
14
16 28
10 14 33 42
11 25 49
Xóa giá tr ị 25
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
15
16 28
10 14 33 42
11 49
Xóa giá tr ị 25
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
16
B-Cây
Btree
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Định nghĩa
ế
ậ
Bcây b c m là 1 cây tìm ki m mnhánh (m>2)
th a:ỏ
Nút gốc có ít nhất 1 khóa
Tất cả các cây con rỗng ở cùng một mức. Tất cả các node (trừ node gốc) có ít nhất (cid:0) m/2(cid:0) cây
con (có ít nhất (cid:0) m/2(cid:0) -1 khóa).
ườ
Giá tr ị m th
ng là l
ẻ .
17
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Ví dụ
26
18
ộ
ậ
M t Bcây có b c là 5
6
12
42
51
62
1
2
4
7
8
13
15
18
25
27
29
45
46
48
53
55
60
64
70
90
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Ví dụ
26
19
ả
Có ph i là Bcây?
6
12
42
51
62
1
2
4
13
15
18
25
27
29
45
46
48
53
55
60
64
70
90
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Tính chất
ọ ộ
ủ
G i đ cao c a cây: h
ố
ố
ủ
ậ
(cid:0)hm
S khóa t
i đa c a Bcây b c m:
20
11 (cid:0)
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thao tác trên cây
Tìm ki mế
Thực hiện tương tự trên cây tìm kiếm m-nhánh.
ầ ử
Thêm ph n t
(khóa)
ầ ử
Xóa ph n t
(khóa)
21
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử
ầ ử
Thêm ph n t
(khóa) vào node lá.
ế
ị
N u node lá b tràn thì
Tách thành 2 node mới.
Khóa chính giữa được đưa lên node cha.
ệ ươ
ự
ự ế
ị
Th c hi n t
ng t
n u node cha b tràn.
22
ế
ữ ệ ậ
ạ
ộ
ị
ố ủ
ữ
ấ
ả i thu t – HCMUS 2010 ố
node cũ)
ấ C u trúc d li u và gi ớ N u node g c b tràn thì t o m t node g c m i (có 1 khóa duy nh t là khóa chính gi a c a
Thêm phần tử - Ví dụ
ầ ử
ậ
ồ
T o Bcây b c 5 g m các ph n t
theo th t
ứ ự
ạ sau:
1, 12, 8, 2, 25, 5, 14, 28, 17, 7, 52, 16, 48, 68, 3, 26,
29, 53, 55, 45
23
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
1 11 1
2 12 8
8 12
12
24
Thêm 1 Thêm 12 Thêm 8 Thêm 2
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
1 11
2
128
12
25
8
1
2
12
25
25
Thêm 25
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
8
1
2
5
12
14
25
28
26
Thêm 5, 14, 28
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
8
1
2
5
12
14
17
25
28
8
17
1
2
5
12
14
25
28
27
Thêm 17
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
8
17
1
2
5
12
14
25
28
8
17
1
2
5
7
12
14
16
25
28
48
52
28
Thêm 7, 52, 16, 48
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
8
17
1
2
5
7
12
14
16
25
28
48
52
68
8
17
48
1
2
5
7
12
14
16
25
28
52
68
29
Thêm 68
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
8
17
48
1
2
3
5
7
12
14
16
25
28
52
68
3
8
17
48
1
2
5
7
12
14
16
25
28
52
68
30
Thêm 3
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
3
8
17
48
1
2
5
7
12
14
16
25
26
28
29
52
53
55
68
31
Thêm 26, 29, 53, 55
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
3
8
17
48
1
2
5
7
12
14
16
25
26
28
29
45
52
53
55
68
3
8
17
28
48
1
2
5
7
12
14
16
25
26
29
45
52
53
55
68
32
Thêm 45
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thêm phần tử - Ví dụ
1 12 8 2 25 5 14 28 17 7 52 16 48 68 3 26 29 53 55 45
3
8
17
28
48
1
2
5
7
12
14
16
25
26
29
45
52
53
55
68
17
28
48
3
8
1
2
5
7
12
14
16
25
26
29
45
52
53
55
68
33
Thêm 45
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Ví dụ
ạ
ồ T o Bcây b c 5 g m các khóa theo th t
ứ ự
ậ
ậ nh p sau đây:
3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56
34
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
ệ ươ
ự
ự
Th c hi n t
ng t
ế cây tìm ki m mnhánh.
ườ
ợ
Xét hai tr
ng h p:
Khóa thuộc node lá
Khóa thuộc node trong
35
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
ộ Khóa thu c node lá:
Xóa khóa khỏi node chứa khóa.
Sau khi xóa, nếu node chứa khóa mới xóa có số khóa
không đủ (ít hơn (cid:0) m/2(cid:0) -1 khóa) thì:
Mượn khóa từ node bên cạnh (Node bên cạnh dư
khóa).
Nhập khóa với node bên cạnh cùng với khóa cha
(Node bên cạnh KHÔNG dư khóa).
36
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
ộ Khóa thu c node trong:
Khóa bị xóa có các node bên nhánh con trái và nhánh con phải có số khóa tối thiểu ((cid:0) m/2(cid:0) -1 khóa): nhập khóa của 2 node con.
Ngược lại: tìm phần tử thế mạng và thực hiện cân
37
bằng lại cây như trường hợp xóa khóa thuộc node lá.
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử
ẫ
ế ằ
ế
ị
Sau khi xóa khóa d n đ n vi c các node trong i lên.
ệ ạ cây b thi u khóa: cân b ng l
ừ ướ d
i cây t
TH1: Nếu node kề phải dư khóa
Thêm khóa cha của 2 node vào node bị thiếu.
Lấy khóa đầu của node kề phải lên thay cho khóa cha
ở node cha.
TH2: Nếu node kề trái dư khóa: làm tương tự trường
hợp trên
38
TH3: Nếu cả node kề trái và phải đều không dư khóa:
Tạo node mới chứa khóa của node bị thiếu, tất cả
khóa của 1 node kề nó và khóa cha của 2 node này.
Xóa khóa cha của 2 node ở node cha, và thay 2 node
con vừa bị nhập bằng node mới tạo.
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29 52
2
7
9
15 22
31 43
56 69 72
39
Xóa khóa 2
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29 52
7
9
15 22
31 43
56 69 72
40
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29 52
7
9
15 22
31 43
56 69 72
41
Xóa khóa 52
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29 56
7
9
15 22
31 43
42
52 69 72
ế ằ Xóa khóa 52. Thay th b ng 56
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29 56
7
9
15 22
31 43
69 72
43
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29 56
7
9
15 22
31 43
69 72
44
Xóa khóa 72
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29 56
7
9
15 22
31 43
69
45
ậ Ít khóa > Nh p node
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29
7
9
15 22
31 43
56
69
46
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29
7
9
15 22
31 43
56
69
47
Xóa khóa 22
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 29
7
9
15
31 43
56
69
48
ượ M n khóa
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
12 31
7
9
15 29
43
56
69
49
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
ồ
ạ Thêm vào các khóa sau trên Bcây b c 5 đã t o (g m các khóa 3, 7, 9, 23, 45, 1, 5, 14, 25, 24, 13, 11, 8, 19, 4, 31, 35, 56):
2, 6,12
ỏ Sau đó, xóa b các khóa sau:
4, 5, 7, 3, 14
50
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
16
3
51
8
28 48
1
2
5
7
12 14
25 26
29 45
52 53
Xóa khóa 8
Nhập 2 node con của 8 lại
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
ậ
Cho Bcây b c 5:
16
3
28 48
1
2
5
7
12
14
25 26
29 45
52 53
ậNode 3 bị thiếu khóa → Cân bằng lại cây theo TH3 Nh n xét?
52
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Xóa phần tử - Ví dụ
→
ạ
ậ
ạ ộ
ớ Cho Bcây b c 5: t o node m i
h đ cao
cây
3 16
28
48
1
2
5
7
12
14
25 26
29 45
52 53
53
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Ý nghĩa
ớ ệ
ằ
ạ
ợ
Bcây là d ng cây cân b ng, phù h p v i vi c
ữ
ư l u tr trên đĩa.
ố
ấ
ố
Bcây tiêu t n s phép truy xu t đĩa t
ể i thi u
ố cho các thao tác.
ầ ử ấ ớ
ể
ố
ả Có th qu n lý s ph n t
r t l n.
54
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Ứng dụng
ỉ ụ
ự
ệ
ấ
ả
Xây d ng c u trúc ch m c trong các h qu n
ị ơ ở ữ ệ tr c s d li u
55
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
56
Cây B+
B+ Tree
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Đặc điểm
ấ ủ
ỏ
Th a tính ch t c a BCây.
ể
ấ
C u trúc c a node lá và node trong có đi m
ủ khác nhau:
Thông tin chỉ mục chứa ở các node trong (không phải
là node lá).
Con trỏ đến vùng dữ liệu của các khóa CHỈ được
chứa ở node lá.
57
ườ
ế
ữ ệ ậ ả i thu t – HCMUS 2010
ạ i
ữ ố
ng có các liên k t qua l ế
(gi ng danh sách liên k t)
ấ C u trúc d li u và gi Gi a các node lá th
Ví dụ
58
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Ví dụ
59
Perryridge
Mianus Redwood
Brighton Downtown Mianus Redwood Round Hill
Perryridge
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Các thao tác trên cây B+
Thao tác thêm, xóa ph n t
ầ ử :
Thực hiện gần giống B-cây.
60
Lưu ý: các khóa nằm ở cây con phải có thể có giá trị lớn hơn hoặc bằng khóa trên node cha tương ứng.
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
61
Tập tin chỉ mục IDX
ỉ ụ
ủ
ệ
ả
ị ơ ở ữ T p tin ch m c c a h qu n tr c s d
ậ ệ li u FoxPro
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Tập tin chỉ mục IDX
ủ
ệ
ả
ị
ị ơ ở T p tin đ nh d ng .IDX c a h qu n tr c s
ậ ữ ệ
ạ d li u Foxpro.
ử ụ
ỉ ụ
ữ ệ
ấ
ư
L u tr ch m c cho d li u s d ng c u trúc
ữ cây B+.
Tham kh o: ả Index File Structrue (.idx) trong
MSDN
62
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Cấu trúc tập tin
ầ
ồ
G m 2 ph n chính:
Header
63
Header file (512 byte)
Dữ liệu: tập hợp các node của cây B+
Node 1
Kích th
c:ướ
Node 2
Header: 512 byte
…
Node: 512 byte
Node N
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Thông tin header
64
00 – 03 Pointer to the root node 04 – 07 Pointer to the free node list ( 1 if not
Header file (512 byte) present)
08 – 11 Pointer to the end of file (file size)
Node 1 12 – 13 Length of key
14
Node 2
Index options (any of the following numeric values or their sums): 1 – a unique index 8 – index has FOR clause Index signature (for future use) … 15
16 – 235 Key expression (uncompiled; up to 220
characters) Node N
236 – 455 FOR expression (uncompiled; up to 220 characters ending with a null value byte)
456 – 511 Unused ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Cấu trúc node
65
Header file (512 byte)
00 – 01 Node attributes (any of the following numeric values or their sums): 0 – index node; 1 – root node; 2 – leaf node
Node 1
02 – 03 Number of keys present (0, 1 or many) 04 – 07 Pointer to the node directly to left of the
current node (on same level; 1 if not)
Node 2 08 – 11 Pointer to the node directly to right of the
current node (on same level; 1 if not)
12 – 511 Up to 500 characters containing the key
…
Node N
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010 value for the length of the key with a four byte hexadecimal number stored in normal lefttoright format: If the node is a leaf (attribute = 02 or 03) then the four bytes contain an actual table number in hexadecimal format; otherwise, the 4 bytes contain an intraindex pointer.
Ví dụ
Ph n t
66
ầ ử ỉ ụ ủ ch m c c a node
ủ ậ
ấ
C u trúc cây B+ c a t p tin IDX
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Hỏi và Đáp
67
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
68
Chỉ mục
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Giới thiệu
69
ụ ự ế
Hãy nêu nh ng ví d th c t
ế ề ỉ ụ
ữ t v ch m c?
đã bi
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Giới thiệu
70
ỉ ụ
ợ
ủ L i ích c a ch m c?
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Giới thiệu
ữ
ư
ể
ậ
ớ
ớ
Các khuy t đi m l n v i cách l u tr trên t p
ế ầ ự :
tin tu n t
Tốc độ tìm kiếm chậm
Không an toàn
Không có nhiều tiêu chí tìm kiếm khác nhau
71
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Định nghĩa
ỉ ụ
Ch m c:
Là một tập hợp các phần tử chỉ mục (Index entry)
Được tổ chức theo một qui tắc xác định nhằm tăng
tốc độ tìm kiếm trên bảng dữ liệu
ỉ ụ
ồ
ố
Ph n t
ấ ch m c: là c u trúc g m t
ể i thi u 2
ầ ử ộ thu c tính:
Khóa tìm kiếm: một (hay nhiều) thuộc tính, được dùng
để tìm kiếm các mẫu tin trong bảng dữ liệu
72
Tham chiếu: con trỏ tham chiếu đến vị trí mẫu tin
ấ ữ ệ ả C u trúc d li u và gi i thu t – HCMUS 2010
ậ tương ứng với Khóa tìm kiếm
Tính chất của chỉ mục
ướ
ớ ả
ỏ ơ
ữ ệ
ề
Kích th
c nh h n nhi u so v i b ng d li u
ự
ệ
ế
Th c hi n tìm ki m nhanh
ề
Cho phép ‘nhìn’ d li u
ữ ệ ở nhi u góc đ khác ề
ộ ế
ế
nhau. (Tìm ki m trên nhi u khóa tìm ki m khác nhau)
73
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
74
Các loại chỉ mục
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Các loại chỉ mục
ỉ ụ
ặ Ch m c dày đ c (Dense index):
Các phần tử chỉ mục được tạo riêng cho mỗi khóa tìm
kiếm
Trong trường hợp trùng khóa, tham chiếu sẽ trỏ đến
bản ghi đầu tiên
ỉ ụ
ư
Ch m c th a (Sparse index)
Tạo phần tử chỉ mục cho một nhóm các khóa tìm
kiếm.
Sử dụng trong trường hợp khóa tìm kiếm đã được
75
ấ ậ ả i thu t – HCMUS 2010
ữ ệ C u trúc d li u và gi sắp xếp
Chỉ mục dày đặc
76
ươ ươ 1 An D ng V ng
ươ ươ An D ng V ng ễ 217 Nguy n Văn A ạ 2 Cách M ng Tháng 8
ạ ị Cách M ng Tháng 8 ầ 101 Tr n Th B ễ ừ 4 Nguy n Văn C
ạ Cách M ng Tháng 8 110 Hoàng Ng c Mọ 7 Phan Xích Long
ễ ừ Nguy n Văn C 215 Lý Minh K ầ 8 Tr n Phú
ễ ừ Nguy n Văn C 423 Vũ Qu c Cố ế 10 Xô Vi ệ t Ngh Tĩnh
ễ ừ Nguy n Văn C 192 Lê Nguy n Uễ
Phan Xích Long 218 Quách P
ầ Tr n Phú ầ 222 Tr n Đăng O
ầ ỳ Tr n Phú 305 Phan Qu nh L
ế ị Xô Vi ệ t Ngh Tĩnh ặ 1234 Đ ng Th G
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Chỉ mục thưa
77
ươ ươ 1 An D ng V ng
ươ ươ An D ng V ng ễ 217 Nguy n Văn A ễ ừ 4 Nguy n Văn C
ạ ị Cách M ng Tháng 8 ầ 101 Tr n Th B 7 Phan Xích Long
ạ Cách M ng Tháng 8 110 Hoàng Ng c Mọ
ễ ừ Nguy n Văn C 215 Lý Minh K
ễ ừ Nguy n Văn C 423 Vũ Qu c Cố
ễ ừ Nguy n Văn C 192 Lê Nguy n Uễ
Phan Xích Long 218 Quách P
ầ Tr n Phú ầ 222 Tr n Đăng O
ầ ỳ Tr n Phú 305 Phan Qu nh L
ế ị Xô Vi ệ t Ngh Tĩnh ặ 1234 Đ ng Th G
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Nhận xét
ế
ặ
ả
V c b n, ch m c dày đ c cho k t qu tìm ỉ ụ
ề ơ ả ế
ư
ỉ ụ ơ ki m nhanh h n ch m c th a.
ử ụ
ỉ ụ
ư
ư
ữ Ch m c th a s d ng ít không gian l u tr
h n.ơ
ế ợ
ỉ ụ
ỉ ụ
ư
ữ ề ầ
ụ
ỉ >K t h p gi a ch m c dày và ch m c th a: ch m c nhi u t ng.
78
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Chỉ mục nhiều tầng
ề ấ V n đ :
Ngay cả khi sử dụng chỉ mục thưa, tập tin chỉ mục
cũng có thể có kích thước lớn.
Giả sử: dữ liệu có 100.000 bản ghi.
Đánh chỉ mục thưa cho từng khối 10 bản ghi
(cid:222) Tổng cộng có 10.000 phần tử chỉ mục
Nếu kích thước chỉ mục không nằm thể nằm trọn
trong bộ nhớ trong => tốn chi phí cho việc đọc tập tin.
79
(Khoảng 14 lần cho dữ liệu 10.000 phần tử chỉ mục) C u trúc d li u và gi i thu t – HCMUS 2010
ữ ệ ậ ấ ả
Chỉ mục nhiều tầng
ụ M c tiêu:
Giảm thiểu số lần truy cập bộ nhớ phụ
ả
Gi
i pháp:
Tạo chỉ mục chính cho dữ liệu (lưu trên bộ nhớ phụ)
Tạo chỉ mục thưa trên chỉ mục chính vừa tạo.
Chỉ mục thưa sẽ lưu trữ trên bộ nhớ chính.
Nếu kích thước của chỉ mục thưa lớn thì có thể tạo
thêm chỉ mục thưa trên đấy.
80
ữ ệ ấ ả ậ C u trúc d li u và gi i thu t – HCMUS 2010
Chỉ mục nhiều tầng
81
ư ầ ỉ ụ Ch m c th a t ng 1
Ch m c th a t ng 2 ữ ệ ấ ư ầ ậ ỉ ụ ỉ ụ ả C u trúc d li u và gi i thu t – HCMUS 2010 Ch m c chính
