11
PHÂN TÍCH THIẾT KẾ THUẬT TOÁN
B-TREES
Nhóm 7: Sử Minh Đạt
Phan Nguyễn Ý Nhi
Cung Nguyễn Phước Tài

Trần Hữu Tấn
Lê Thị Thanh Thủy
GVHD: TS. HOÀNG QUANG
2
2
NỘI DUNG TRÌNH BÀY
1.Tổng quan: Trần Hữu Tấn
2. Định nghĩa: Cung Nguyễn Phước Tài
3.Thủ tục tìm kiếm, tạo: Lê Thị Thanh Thủy
4.Thủ tục chèn, tách: Sử Minh Đạt
5.Thủ tục xóa: Phan Nguyễn Ý Nhi
3
3
TỔNG QUAN
- B-tree là cấu trúc dữ liệu phù hợp cho việc lưu trữ ngoài do
R.Bayer và E.M.McCreight đưa ra năm 1972.
- B-tree là cây tìm kiếm cân bằng.
- B-tree tương tự như cây đỏ đen.
4
4
So sánh giữa B-tree và cây Đỏ Đen:
- Giống nhau:
+ Cây cân bằng.
+ Cây có n nút đều có chiều cao là O(lg n).

- Khác nhau:
B-tree Cây Đỏ Đen
Một nút có thể có một đến
hàng ngàn nút con.
Một nút có tối đa 2 nút
con.
TỔNG QUAN (tt)
5
5
TỔNG QUAN (tt)
Thời gian tìm kiếm trên B-Tree rất nhanh, cho nên cây
này thường được dùng để quản lý cơ sở dữ liệu và công
cụ tìm kiếm như Google đều dùng B-Tree.
- Sự quay của đĩa.
- Sự chuyển động của cần điều khiển.
Rãnh từTrục xoay
Đầu đọc ghi
Bề mặt đĩa
Rãnh từ
Cần điều khiển
Một ổ đĩa từ thông thường.
6
6
TỔNG QUAN (tt)
Có hai thao tác chính mà B-Tree thường sử dụng là:
- Thao tác DISK-READ(x) để đọc đối tượng x vào bộ nhớ
chính trước khi chúng ta yêu cầu những trường của nó.
- Thao tác DISK-WRITE(x) được sử dụng để lưu trữ bất cứ
thay đổi nào tác động đến các trường của đối tượng x.
Vì trong hầu hết các hệ thống, thời gian thực thi của thuật

toán cây B-tree được quyết định chính bởi số lượng các thao
tác DISK-READ và DISK-WRITE được thực hiện, điều này
cho thấy việc sử dụng những thao tác trên càng hiệu quả sẽ
dẫn đến việc đọc và ghi thông tin càng nhiều. Vì vậy, một nút
của B-tree thường có kích thước rộng bằng với toàn bộ một
trang trên đĩa. Do đó số lượng nút con của nó có thể bị giới
hạn bởi kích thước một trang trên đĩa.
7
VÍ DỤ MINH HỌA

Một B-Tree có khóa là các phụ âm tiếng anh.
7
root[T]: Con trỏ trỏ đến nút gốc.
8
ĐỊNH NGHĨA B-TREE

Một B-Tree có gốc T có các tính chất:
–
Một nút x trên cây có các trường sau:
•
n[x] : Số các khóa hiện tại được lưu tại nút x.
•
key
i
[x] : Một khóa thứ i được lưu tại nút x.
(với 1<=i<j<=n[x], thì key
i
[x]<=key
j
[x])

•
leaf[x] : nhận giá trị TRUE nếu x là nút lá, nhận giá trị FALSE
nếu x không là nút lá (nút thường).
8
key
1
[x]
key
2
[x]
leaf[x]=false
9
TÍNH CHẤT B-TREE
- Mỗi nút thường x chứa n[x] + 1 con trỏ: c
1
[x], c
2
[x], ,
c
n[x]+1
[x] trỏ tới các nút con của nó. Các nút lá không có
nút con do vậy trường c
i
của nó không được định nghĩa.
9
c
1
[x]
c
2

[x] c
3
[x]
10
TÍNH CHẤT B TREE (tt)
–
Các khoá key
i
[x] tách thành các vùng khóa và được
lưu trữ thành mỗi cây con tương ứng: nếu k
i
là một
khoá bất kỳ được lưu trữ trong cây con có gốc là c
i
[x] thì
k
1
≤ key
1
[x] ≤ k
2
≤ key
2
[x] ≤··· ≤ key
n[x]
[x] ≤ k
n[x]+1
.
–
Tất cả các nút lá có cùng chiều cao h.

10
k
1
= C
key
1
[x]=D
11
TÍNH CHẤT B-TREE (tt)
–
Số lượng các khoá của một nút nằm trong một biên
giới hạn được diễn tả bằng một số nguyên có giá trị
không đổi t (t ≥ 2) được gọi là mức tối thiểu của B-
Tree:
•
Các nút không phải là nút gốc phải có ít nhất t-1 khoá.
•
Mỗi nút thường trừ nút gốc có ít nhất t nút con.
•
Nếu cây không rỗng thì nút gốc phải có ít nhất 1 khoá.
•
Mỗi nút có thể chứa tối đa 2t-1 khoá (được gọi nút
đầy).
11
12
ĐỊNH LÝ

Nếu n ≥ 1 thì với bất kỳ B-Tree T n khóa, có mức tối
thiểu t ≥ 2 thì có chiều cao:
)

2
1
(log
+
≤
n
h
t
13
CÁC PHÉP TOÁN CƠ BẢN TRÊN B-TREE.

Trong phần này, ta trình bày các chi tiết của các phép toán
B-TREE-SEARCH, B-TREE-CREATE, và B-TREE-INSERT.
Trong các thủ tục này, ta chấp nhận 2 quy ước:
 Gốc của B-Tree luôn nằm trong bộ nhớ chính, để
không bao giờ cần thực hiện một DISK-READ trên gốc; tuy
nhiên, ta cần một DISK-WRITE của gốc, mỗi khi nút gốc thay
đổi.
 Mọi nút được chuyền dưới dạng các tham số phải
có sẵn một phép toán DISK-READ được thực hiện trên
chúng.
14
TÌM KIẾM KHÓA TRONG B-TREE

Tìm kiếm trong một B-Tree cũng giống như tìm kiếm trong một
cây tìm kiếm nhị phân, thay vì thực hiện rẽ nhánh “2-chiều” tại
mỗi nút, ta thực hiện rẽ nhánh đa chiều theo số lượng các con
của nút.Tại mỗi nút trong x, ta thực hiện rẽ nhánh (n[x] + 1)
chiều.
 B-TREE-SEARCH chấp nhận dưới dạng nhập liệu

một biến trỏ đến nút gốc x của một cây con và một khóa k để
tìm kiếm trong cây con đó.
 Như vậy lệnh gọi trên cùng có dạng B-TREE-
SEARCH (root[T], k). Nếu k nằm trong B-Tree, B-TREE-
SEARCH trả về cặp có thứ tự (y, i) bao gồm một nút y và một
chỉ số i sao cho key
i
[y] = k. Ngược lại, giá trị NIL được trả về.
15
TÌM KIẾM KHÓA TRONG B-TREE
B-TREE-SEARCH(x, k)
1 i ← 1
2 while i ≤ n[x] and k > key
i
[x]
3 do i ← i + 1
4 if i ≤ n[x] and k = key
i
[x]
5 then return (x, i)
6 if leaf [x]
7 then return NIL
8 else DISK-READ(c
i
[x])
9 return B-TREE-SEARCH(c
i
[x],k)
16
Ví dụ: Cho B-Tree có độ cực tiểu t=2. Tìm khóa 35?

50 52
25
10 2010 20
30 40 50
5 7 8
13 15 18
22 24 26 27
32 35 38 42 45 46
A
B
D
E
F G
H
I
J
C
Hình 4
TÌM KIẾM KHÓA TRONG B-TREE.
17
B-TREE-SEARCH(x, k)
1 i ← 1
2 while i ≤ n[x] and k > key
i
[x]
3 do i ← i + 1
4 if i ≤ n[x] and k = key
i
[x]
5 then return (x, i)

6 if leaf [x]
7 then return NIL
8 else DISK-READ(c
i
[x])
9 return B-TREE-SEARCH(c
i
[x],k)
50 52
25
10 2010 20
30 40 50
5 7 8
13 15 18
22 24 26 27
32 35 38 42 45 46
A
B
D
E
F G
H
I
J
C
1. B-TREE-SEARCH(A, 35)
i=2, DISK-READ(c
2
[A])
2. B-TREE-SEARCH(C, 35)

i=2, DISK-READ(c
2
[C])
3. B-TREE-SEARCH(H, 35)
i=2, return (H, 2)
TÌM KIẾM KHÓA TRONG B-TREE
18
Nhận xét:
 Số lượng các trang đĩa mà B-TREE-SEARCH truy cập
là O(h) = O(log
t
n), ở đó h là chiều cao của B-Tree, t là độ
cực tiểu và n là số lượng khóa trong B-Tree.
 Do n[x] < 2t, nên thời gian mà vòng lặp while của các
dòng 2-3 trải qua trong mỗi nút là O(t), và tổng thời gian
CPU là O(th) = O(t log
t
n).
TÌM KIẾM KHÓA TRONG B-TREE
19
 Để xây dựng một B-Tree, trước tiên ta dùng B-TREE-
CREATE để tạo một nút gốc trống rồi gọi B-TREE-INSERT để
bổ sung các khóa mới.
 Cả hai thủ tục này dùng một thủ tục phụ ALLOCATE-
NODE, phân bổ một trang đĩa sẽ được dùng làm một nút mới
trong O(1) thời gian.
 Ta có thể mặc nhận một nút mà ALLOCATE-NODE tạo
không yêu cầu DISK-READ.
TẠO MỘT B-TREE TRỐNG
20

B-TREE-CREATE(T)
1 x ALLOCATE-NODE()
2 leaf [x] TRUE
3 n[x] 0
4 DISK –WRITE(x)
5 root[T] x
→ B-TREE-CREATE yêu cầu O(1) phép toán đĩa và O(1) thời
gian CPU.
TẠO MỘT B-TREE TRỐNG
21
CHÈN MỘT KHÓA VÀO B-TREE

Tách một nút đầy

Chèn một khoá vào B-tree
22
TÁCH MỘT NÚT ĐẦY

Khi chèn khóa vào một lá của cây, để tránh trường hợp
chèn khóa vào một lá đã đầy, ta cần một thao tác tách
(split) một nút đầy y. Thao tác này gồm các bước:
–
Xác định khoá giữa (trung tuyến) của nút đầy y là khoá
key
t
[y].
–
Tách nút đầy y tại khóa giữa của nó thành hai nút, mỗi
nút có t - 1 khóa và t nút con.
–

Di chuyển khóa trung tuyến lên nút cha của y là x (x phải
là nút không đầy) vào một vị trí “thích hợp”
23
VÍ DỤ TÁCH MỘT NÚT ĐẦY

Bậc tối thiểu của cây là t =4.

Số nút tối đa của một nút là 7

Tách nút đầy y là con của nút không đầy x
⋅⋅⋅ N W ⋅⋅⋅
P Q R S T U V
x
y = c
i
[x]
P Q R
y = c
i
[x] z = c
i +1
[x]
T U V
⋅⋅⋅ N W ⋅⋅⋅
S
x
P Q R S T U V
S
24
TÁCH MỘT NÚT ĐẦY (TT)


Thủ tục B-TREE-SPLIT-CHILD
–
Input: một nút trong không đầy x, một chỉ số i mà nút y = c
i
[x] là
một nút đầy
–
Output: thủ tục tách y thành 2 nút và chỉnh x để cho x có thêm
một nút con
25
TÁCH MỘT NÚT ĐẦY (TT)
B-TREE-SPLIT-CHILD(x, i, y)
1 z ← ALLOCATE-NODE()
2 leaf [z] ← leaf [y]
3 n[z] ← t − 1
4 for j ← 1 to t − 1
5 do key
j
[z] ← key
j + t
[y]
6 if not leaf [y]
7 then for j ← 1 to t
8 do c
j
[z] ← c
j + t
[y]
9 n[y] ← t − 1

10 for j ← n[x] + 1 downto i + 1
11 do c
j

+1
[x] ← c
j
[x]
12 c
i

+1
[x] ← z
13 for j ← n[x] downto i
14 do key
j +1
[x] ← key
j
[x]
15 key
i
[x] ← key
t
[y]
16 n[x] ← n[x] + 1
17 DISK-WRITE(y)
18 DISK-WRITE(z)
19 DISK-WRITE(x)
}
Dòng 1-8 tạo nút z và cho nó t - 1

khóa lớn hơn và t nút con của y
Điều chỉnh số khóa của y
}
Dòng 10-16 chèn z dưới dạng
một con của x, dời khóa trung
tuyến từ y lên x để tách biệt y và
z, và điều chỉnh số khóa của x
}
Dòng 17-19 ghi ra tất cả các
trang đĩa được thay đổi