ĐẠI HỌC HUẾ
ĐẠI HỌC KHOA HỌC HUẾ
KHOA CÔNG NGHỆ THÔNG TIN
*****
TIỂU LUẬN
PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN
Đề tài :
GVHD: TS. Hoàng Quang
LỚP: Khoa học máy tính 2012 -2014
HVTH: 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
B-TREES
Huế, 10/2014
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 2
B-TREES
CHƯƠNG 18: B-TREES
Tổng quan
B-trees là những cây tìm kiếm cân bằng được thiết kế để làm việc tốt
trên những ổ đĩa từ tính hay những thiết bị lưu trữ phụ được truy xuất trực
tiếp khác. B-tree tương tự như cây đỏ-đen (chương 13), nhưng chúng tối ưu
hóa hơn cho những thao tác vào ra dữ liệu trên ổ đĩa. Nhiều hệ thống cơ sở dữ
liệu sử dụng B-tree, hay biến thể của B-tree để lưu trữ thông tin.
B-tree khác cây đỏ-đen ở chỗ một nút của B-tree có thể có một đến
hàng ngàn nút con. Nói cách khác, một yếu tố nhánh của B-tree có thể khá
rộng, mặc dù nó thường được quy định bởi đặc điểm của ổ đĩa được sử dụng.
B-tree tương tự với cây đỏ-đen ở chỗ mọi B-tree có n nút đều có chiều cao là
O(lg n), mặc dù chiều cao của một B-tree có thể xem như ít hơn chiều cao của

cây đỏ-đen bởi vì yếu tố nhánh của nó có thể rộng hơn. Vì vậy, B-tree cũng
có thể sử dụng để thực thi nhiều tác vụ động có độ phức tạp O(lg n).
Theo cách hiểu thông thường, B-tree có thể tổng quát hóa những cây
nhị phân tìm kiếm. Hình 18.1 thể hiện một B-tree đơn giản. Nếu một nút x
bên trong B-tree chứa n[x] khóa thì x có n[x] + 1 con. Những khóa trong nút x
được sử dụng như những điểm phân chia vùng khóa của nút x thành n[x] + 1
vùng con, mỗi vùng con này được xử lý như một nút con của nút x. Khi tìm
kiếm một khóa trên B-tree, chúng ta thực hiện n[x] + 1 cách dựa trên việc so
sánh với n[x] khóa được lưu trữ ở nút x. Cấu trúc của các nút lá khác nhau với
các nút thường (chúng ta sẽ khảo sát những sự khác nhau đó ở phần 18.1).
Hình 18.1: Một B-tree có khóa là các phụ âm tiếng anh. Một nút x bên
trong chứa n[x] khóa tương ứng với n[x]+1 nút con. Tất cả các nút con có
cùng một độ cao giống nhau trong cây. Những nút tô màu nhạt sẽ được khảo
sát để tìm kiếm ký tự R.
Phần 18.1 sẽ định nghĩa chính xác B-tree là gì và chứng minh rằng
chiều cao của B-tree sẽ tăng dần theo hàm logarit số lượng nút con của nó.
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 3
B-TREES
Phần 18.2 sẽ mô tả bằng cách nào để tìm kiếm một khóa và chèn một khóa
vào B-tree, và phần 18.3 trình bày việc xóa một khóa. Tuy nhiên, trước khi
tiến hành chúng ta cần phải biết tại sao cấu trúc dữ liệu được thiết kế để làm
việc trên đĩa từ được đánh giá khác biệt hơn cấu trúc dữ liệu được thiết kế để
làm việc trên bộ nhớ chính truy xuất ngẫu nhiên.
Những cấu trúc dữ liệu trên bộ nhớ thứ cấp
Có nhiều công nghệ khác nhau được sử dụng để cung cấp dung lượng
nhớ bên trong hệ thống máy tính. Bộ nhớ chính của một hệ thống máy tính
thông thường bao gồm nhiều chip nhớ silicon. Công nghệ này là điển hình
cho hai giải pháp lưu trữ quan trọng có chi phí lưu trữ trên mỗi bit đắt hơn
nhiều so với công nghệ lưu trữ từ tính như là băng từ hay đĩa từ. Hầu hết
những hệ thống máy tính đều có bộ nhớ thứ cấp dựa trên các đĩa từ tính; dung

lượng của những bộ nhớ thứ cấp như vậy thường lớn hơn dung lượng của bộ
nhớ chính ít nhất là hai lần đơn vị độ lớn.
Hình 18.2(a) minh họa một ổ đĩa thông thường. Nó bao gồm nhiều đĩa
(platter) quay xung quanh một trục thẳng đứng (spindle) với một tốc độ ổn
định. Bề mặt của mỗi đĩa được bao phủ bởi một lớp từ tính. Mỗi đĩa được đọc
và ghi bởi một đầu đọc ghi (head) ở cuối một cần điều khiển (arm). Những
cần điều khiển này được gắn với nhau thành một khối và chúng di chuyển
những đầu đọc ghi hướng đến hay đi ra xa đĩa từ. Khi một đầu đọc ghi dừng
lại, bề mặt được tiếp xúc bên dưới nó được gọi là một rãnh từ (track). Các
đầu đọc ghi được canh chỉnh theo phương dọc ở mọi lúc vì vậy một tập các
rãnh từ ở bên dưới chúng được truy xuất đồng thời. Hình 18.2(b) minh họa
một tập các rãnh từ như thế mà chúng được gọi là một hình trụ đồng tâm
(cylinder).
Hình 18.2: (a) Một ổ đĩa từ thông thường. Nó được tạo nên bởi nhiều
đĩa quay xung quanh một trục thẳng đứng. Mỗi đĩa được đọc và ghi bởi một
đầu đọc ở cuối một cần điều khiển. Những cần điều khiển gắn kết với nhau vì
vậy chúng di chuyển đồng bộ các đầu đọc ghi. Ở đây, những cần điều khiển
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 4
B-TREES
quay xung quanh một trục hình trụ. Một rãnh từ là bề mặt tiếp xúc bởi đầu
đọc ghi khi nó dừng lại. (b) Một hình trụ đồng tâm bao gồm một tập các rãnh
từ trên đĩa theo phương dọc.
Mặt dù những ổ đĩa rẻ hơn và có dung lượng lớn hơn bộ nhớ chính
nhưng chúng chậm hơn nhiều bởi vì chúng có nhiều bộ phận di chuyển. Có
hai thành phần di chuyển cơ học đó là: sự quay của đĩa và sự chuyển động của
cần điều khiển. Theo đó, những ổ đĩa được sản xuất có tốc độ quay khoảng
5400-15000 vòng mỗi phút (RPM), thường tốc độ quay 7200 RPM là phổ
biến. Dù 7200 RPM xem ra có vẻ nhanh, tức là mỗi vòng mất khoảng 8.33 lần
một phần nghìn giây, tính ra thời gian đó gần bằng 5 lần thời gian truy xuất
của bộ nhớ silicon thông thường với 100 lần một phần tỉ giây. Nói cách khác,

nếu chúng ta phải chờ một vòng quay đầy đủ của một phần tử đặc thù nào đó
để tiếp xúc dưới đầu đọc ghi, chúng ta có thể truy xuất bộ nhớ chính hầu như
gần 100,000 lần trong suốt khoảng thời gian ngắn đó! Tính trung bình chúng
ta phải chờ chỉ một nữa vòng quay, nhưng như thế sự khác biệt về thời gian
truy xuất giữa bộ nhớ silicon và các ổ đĩa từ đã là khổng lồ. Sự di chuyển các
cần điều khiển cũng mất một lượng thời gian. Theo đó, thời gian truy xuất
trung bình của các ổ đĩa được sản xuất nằm trong khoảng từ 3 đến 9 lần một
phần nghìn giây.
Để bù lại khoảng thời gian hao phí cho những chuyển động cơ học đó,
các ổ đĩa truy xuất không chỉ một phần tử mà có thể nhiều phần tử tại một
thời điểm. Thông tin được chia thành một số lượng các trang có kích thước
bằng nhau tính bằng bít mà xuất hiện liên tiếp nhau bên trong các hình trụ
đồng tâm, và mỗi đĩa sẽ đọc hoặc ghi với toàn bộ một hay nhiều trang như
thế. Với một đĩa thông thường, một trang có thể có chiều dài từ 2
11
đến 2
14
byte. Mỗi một lần đầu đọc ghi xác định vị trí chính xác cần đến, đĩa sẽ quay
đến điểm bắt đầu của trang yêu cầu, việc đọc hoặc ghi một đĩa từ là hoàn toàn
điện tử (ngoại trừ sự quay của đĩa), theo đó một lượng lớn dữ liệu có thể được
đọc hoặc ghi một cách nhanh chóng.
Việc truy xuất và đọc một trang thông tin từ đĩa thường mất nhiều thời
gian hơn việc máy tính khảo sát tất cả thông tin đọc được. Vì lý do trên, trong
chương này chúng ta sẽ tập trung vào hai yếu tố tách biệt chính của thời gian
thực hiện đó là:
• Số lần truy xuất đĩa
• Và thời gian chiếm CPU.
Số lần truy xuất đĩa được đo lường với thuật ngữ số lượng trang thông
tin cần được đọc hoặc ghi từ đĩa. Chúng ta lưu ý rằng thời gian truy xuất đĩa
không phải hằng số, nó tùy thuộc vào khoảng cách giữa rãnh hiện tại và rãnh

yêu cầu và cũng như là tình trạng khởi điểm quay của đĩa. Dù sao chúng ta sẽ
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 5
B-TREES
sử dụng số lượng trang đọc hoặc ghi như là một đại lượng đầu tiên xấp xỉ gần
đúng với tổng thời gian hao phí cho việc truy xuất đĩa.
Trong một ứng dụng tiêu biểu về B-tree, dữ liệu mà không chứa đủ
trong bộ nhớ chính vẫn có thể được xử lý cùng một lúc. Thuật toán B-tree sao
chép các trang được chọn từ đĩa vào trong bộ nhớ chính khi cần thiết và ghi
trở lại vào đĩa những trang đã bị thay đổi. Thuật toán B-tree được thiết kế để
chỉ một số lượng trang cố định nằm bên trong bộ nhớ chính tại bất cứ thời
điểm nào; vì vậy kích cỡ của bộ nhớ chính không giới hạn kích cỡ dữ liệu có
thể xử lý của B-tree.
Chúng ta mô hình hóa những thao tác vận hành đĩa với đoạn giả mã
như sau. Gọi x là một con trỏ trỏ đến một đối tượng. Nếu đối tượng đó hiện
tại ở trong bộ nhớ chính của máy tính thì chúng ta có thể yêu cầu đến những
trường của đối tượng này, ví dụ như trường key[x]. Tuy nhiên, nếu đối tượng
chỉ dẫn bởi x vẫn còn nằm trên đĩa thì chúng ta phải thực thi 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ó. (Ta giả sử rằng nếu x đã sẵn sàng trong bộ nhớ chính,
thì thao tác DISK-READ(x) không truy xuất đĩa hay nói cách khác thao tác
không được thực hiện “no-op”). Tương tự như vậy, 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. Theo đó, một quy trình tiêu biểu cho quá trình làm việc với một đối
tượng như sau:
• Gán x là một con trỏ trỏ đến một đối tượng
• DISK-READ(x)
• Các thao tác truy xuất và/hoặc chỉnh sửa các trường của x
• DISK-WRITE(x): thao tác này sẽ bỏ qua nếu không có bất kỳ trường
nào của x bị thay đổi.
• Những thao tác truy xuất khác nhưng không chỉnh sửa các trường của

x.
Hệ thống chỉ có thể giữ một số lượng hạn chế các trang bên trong bộ
nhớ chính ở bất cứ thời điểm nào. Chúng ta có thể giả định rằng các trang
không còn sử dụng nữa sẽ bị đẩy ra khỏi bộ nhớ chính bởi hệ thống; thuật
toán B-tree sẽ lờ đi những trang này.
Vì trong hầu hết các hệ thống, thời gian thực thi của thuật toán 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.
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 6
B-TREES
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.
Với một B-tree lưu trữ trên đĩa, số các yếu tố nhánh của nó thường sử
dụng khoảng từ 50 đến 2000, tùy thuộc vào kích thước của một khóa mà có
liên quan đến kích thước của một trang. Một yếu tố nhánh lớn được rút ngắn
cả về chiều cao của cây và số lần truy xuất đĩa được yêu cầu để tìm bất kỳ
một khóa nào đó. Hình 18.3 thể hiện một B-tree với 1001 yếu tố nhánh và có
chiều cao 2 mà có thể lưu trữ trên một tỉ khóa; tuy thế, do nút gốc có thể được
nạp thường trực vào bộ nhớ chính nên hầu như chỉ yêu cầu hai lần truy xuất
đĩa để tìm ra bất cứ khóa nào trên cây này!
Hình 18.3: Một B-tree có chiều cao 2 chứa trên một tỉ khóa. Mỗi nút
thường và nút lá chứa 1000 khóa. Có 1001 nút có chiều cao là 1 và trên một
triệu nút có chiều cao 2. Số khóa của nút x là giá trị bên trong nút x đó là
n[x].
18.1. Định nghĩa B-trees
Để đơn giản, chúng ta giả sử có các cây nhị phân tìm kiếm và các cây
đỏ đen mà bất cứ thông tin đi kèm nào kết hợp với một khoá được lưu trữ
trong cùng một nút với khóa đó. Trong thực tế, có thể lưu trữ mỗi khóa như là

một con trỏ trỏ đến một trang nhớ khác chứa thông tin đi kèm của khoá đó.
Trong chương này, toàn bộ phần giả mã ngầm định rằng thông tin đi kèm của
một khoá, hay là con trỏ trỏ đến thông tin đi kèm đó, sẽ luôn đi cùng với khoá
này bất cứ khi nào nó được di chuyển từ nút này sang nút khác. Một biến thể
thông thường của B-tree là cây B
+
-tree. Cây này lưu trữ các thông tin đi kèm
tại các nút lá và chỉ lưu trữ các khoá và các con trỏ con trong các nút thường,
vì vậy làm cực đại hoá yếu tố nhánh của các nút thường.
Một B-tree T là một cây có gốc (gốc của nó là root[T]) có các tính chất
sau:
1. Mỗi nút x có các trường sau đây:
a. n[x] là số các khoá hiện tại được lưu trữ trong nút x
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 7
B-TREES
b. Các khoá n[x] của nó được lưu trữ theo thứ tự không giảm, vì
vậy: key
1
[x] ≤key
2
[x] ≤ ··· ≤ key
n
[x][x]
c. leaf[x] là một giá trị logic nhận giá trị TRUE nếu x là nút lá và
FALSE nếu x là nút thường.
2. Mỗi nút thường x cũng 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.
3. 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
.
4. Tất cả các nút lá có cùng chiều cao h
5. Số lượng các khoá mà một nút có thể chứa nằm trong một biên giới
hạn. Những biên này có thể diễn tả bằng một số nguyên có giá trị

không đổi t ≥ 2 được gọi là có mức tối thiểu của B-tree:
a. 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 ngoại trừ nút gốc thì 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 một khoá.
b. Mỗi nút có thể chứa tối đa 2t-1 khoá. Vì vậy, một nút thường có
thể có tối đa 2t nút con. Ta nói rằng một nút là đầy nếu nó chứa
chính xác 2t -1 khoá.
Một B-tree đơn giản nhất khi t=2. Khi đó, mọi nút thường có 2, 3 hoặc
4 nút con và ta có một cây 2-3-4. Tuy nhiên trong thực tế, người ta thường
dùng các giá trị t lớn hơn nhiều.
Chiều cao của một B-tree
Số lần truy xuất đĩa đòi hỏi cho hầu như các thao tác trên một B-tree tỉ
lệ với chiều cao của nó. Bây giờ, chúng ta phân tích chiều cao của một B-tree
trong trường hợp xấu nhất.h
Định lý 18.1
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
Chứng minh: Nếu một B-tree có chiều cao h thì nút gốc chứa ít nhất 1 khoá và
tất cả các nút khác chứa ít nhất t-1 khoá. Như vậy có ít nhất 2 nút có chiều cao
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 8
B-TREES
là 1, ít nhất 2t nút có chiều cao là 2, ít nhất 2t

2
nút có chiều cao là 3, … cho
tới khi tại chiều cao h sẽ có ít nhất 2t
h-1
nút. Hình 18.4 minh họa một cây như
vậy với chiều cao h = 3. Vì vậy với n khoá thoả mãn bất đẳng thức đề ra.
Bằng các thao tác đại số đơn giản, ta có t
h
<= (n+1)/2. Lấy logarit cơ số
t cả hai vế ta có điều phải chứng minh.
Ở đây, chúng ta thấy điểm mạnh của B-tree so với cây đỏ-đen. Mặc dù
chiều cao là O(lg n) trong cả hai trường hợp (lưu ý rằng t là một hằng số), thì
cơ số logarít của B-tree có thể lớn hơn nhiều lần so với cây đỏ-đen. Vì vậy,
trong hầu hết các thao tác, B-tree tiết kiệm hơn cây đỏ-đen một khoảng là lg t
với cùng một số lượng nút được khảo sát. Bởi vì việc khảo sát một nút tuỳ ý
trên cây thường đòi hỏi một lần truy xuất đĩa, nên số lần truy xuất đĩa được
giảm đáng kể.
18.2 Các thao tác cơ bản trên B-tree
Trong phần này, chúng ta sẽ giới thiệu chi tiết các thao tác tìm kiếm (B-
TREE-SEARCH), khởi tạo (B-TREE-CREATE) và chèn (B-TREE-INSERT)
trên một B-tree. Trong các thủ tục đó, ta chấp nhận 2 quy ước:
- Nút gốc của B-tree luôn ở trong bộ nhớ chính, nên một thao tác
DISK-READ trên nút gốc là không cần thiết; thao tác DISK-
WRITE của nút gốc sẽ được yêu cầu bất cứ khi nào nút gốc bị thay
đổi
- Bất cứ nút nào được duyệt qua bởi các tham số đều phải có một thao
tác DISK-READ được thực thi với nó.
Những thủ tục mà chúng ta giới thiệu dưới đây là những giải thuật “một
hướng”: đi từ trên xuống bắt đầu từ nút gốc và không quay trở lại.
Tìm kiếm trên B-tree

Việc tìm kiếm trên một B-tree tương tự với việc tìm kiếm trên cây nhị
phân tìm kiếm, chỉ khác trên cây nhị phân ở mỗi nút sẽ đi theo 2 nhánh còn
B-tree sẽ đi theo nhiều hướng dựa vào số nút con ở mỗi nút. Chính xác hơn,
mỗi nút thường x, chúng ta cần phải duyệt qua (n[x] +1) nhánh.
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 9
B-TREES
Thủ tục B-TREE-SEARCH là một thủ tục tổng quát của thủ tục TREE-
SEARCH được định nghĩa trên cây nhị phân. Thủ tục B-TREE-SEARCH lấy
đầu vào là một con trỏ trỏ đến nút gốc x của một cây con và một khoá k để tìm
kiếm trên cây con đó. Lệnh gọi thủ tục tìm kiếm mức cao nhất trên B-tree là
B-TREE -SEARCH(root[T], k). Nếu khoá k nằm trong B-tree thì thủ tục B-
TREE -SEARCH trả về cặp thứ tự (y, i) chứa nút y và chỉ mục i với key
i
[y] =
k. Ngược lại, thủ tục trả lại giá trị NIL.
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)
Sử dụng thủ tục tìm kiếm tuần tự, các dòng 1-3 tìm ra chỉ số i nhỏ nhất
sao cho k ≤ key
i
[x], ngược lại chương trình đặt i tại vị trí n[x] +1. Các dòng 4-
5 kiểm tra nếu tìm được khoá cần tìm thì thủ tục trả về kết quả. Các dòng lệnh
từ 6-9 kết thúc quá trình tìm kiếm không thành công (nếu x là một nút lá)
hoặc gọi đệ quy tìm kiếm trên cây con tương ứng của nút x, sau khi đã hoàn
thành thao tác DISK-READ trên nút con tương ứng.
Hình 18.1 minh họa hoạt động của thủ tục B-TREE-SEARCH; các nút
được tô màu nhạt được kiểm tra trong quá trình tìm kiếm khóa R.
Giống như thủ tục TREE-SEARCH trên cây nhị phân tìm kiếm, các nút
được duyệt qua trong quá trình đệ quy hình thành nên đường dẫn đi xuống từ
nút gốc của cây. Vì vậy số lần truy xuất các trang của đĩa bởi thủ tục B-
TREE-SEARCH là O(h) = O(log
t
n), với h là chiều cao của B-tree và n là số
các khoá trong B-tree. Vì n[x] < 2t nên thời gian thực hiện của vòng lặp while
ở câu lệnh 2-3 trong mỗi nút là O(t), và tổng thời gian chiếm CPU là O(th) =
O(t log
t
n).
Tạo một B-tree rỗng
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 10
B-TREES
Để xây dựng một B-tree T, trước tiên chúng ta sử dụng thủ tục B-
TREE-CREATE để tạo 1 nút gốc rỗng và sau đó gọi thủ tục B-TREE-
INSERT để thêm các khoá mới. Cả hai thủ tục này đều sử dụng một thủ tục

bổ trợ đó là ALLOCATE-NODE, thủ tục này định vị một trang của đĩa sử
dụng cho một nút mới trong khoảng thời gian O(1). Chúng ta có thể giả sử
một nút được tạo bởi thủ tục ALLOCATE-NODE không đòi hỏi thao tác
DISK-READ, vì thế chưa có thông tin hữu ích nào được lưu trên đĩa cho nút
này.
B-TREE -CREATE(T)
1 x ← ALLOCATE-NODE()
2 leaf[x] ← TRUE
3 n[x] ← 0
4 DISK-WRITE(x)
5 root[T] ← x
Thủ tục B-TREE-CREATE đòi hỏi O(1) thao tác đĩa và chiếm O(1)
thời gian CPU.
Chèn một khoá vào một B-tree
Việc chèn một khoá vào một B-tree thật sự phức tạp hơn chèn một
khoá vào cây nhị phân tìm kiếm. Giống như cây nhị phân tìm kiếm, ta tìm vị
trí nút lá để chèn thêm vào khoá mới. Tuy nhiên, với B-tree, ta không thể đơn
thuần tạo mới một nút lá và chèn nó vào vì như thế cây mới hình thành sẽ
không còn là B-tree hợp lệ. Thay vào đó, ta chèn khóa mới vào một nút lá
hiện có. Vì ta không thể chèn một khóa mới vào một nút lá đầy, nên cần có
một thao tác chia một nút đầy y (có 2t - 1 khóa) quanh khóa trung tuyến
key
t
[y] của nó thành hai nút có t - 1 khóa cho mỗi nút. Khóa trung tuyến dời
lên vị trí cha của y để chỉ rõ điểm chia giữa hai cây mới. Nhưng nếu nút cha
của y cũng đầy, nó phải được tách ra trước khi khóa mới có thể chèn vào, và
như vậy tiến trình tách các nút đầy là biện pháp để cây tăng trưởng.
Như với một cây nhị phân tìm kiếm, chúng ta có thể chèn một khóa vào
một B-tree trong một cây đơn hướng xuống từ gốc đến lá. Để làm như vậy, ta
không chờ đợi để tìm hiểu xem liệu chúng ta sẽ thực sự cần tách một nút đầy

để thực hiện việc chèn hay không. Thay vào đó, khi ta dò xuống cây để tìm
kiếm vị trí chứa khóa mới, ta chia mỗi nút đầy gặp phải dọc theo đường đi
(bao gồm nút lá của nó). Vì vậy, bất cứ khi nào chúng ta muốn chia một nút
đấy y, thì yên tâm rằng cha của nó là không đầy.
Tách một nút trong một B-tree
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 11
B-TREES
Thủ tục B-TREE-SPLIT-CHILD lấy đầu vào gồm một nút thường
không đầy x (giả sử có trong bộ nhớ chính), một chỉ số i, và một nút y (cũng
giả sử có trong bộ nhớ chính) sao cho y = c
i
[x] là một con đầy của x. Như vậy,
thủ tục tách nút con này thành hai và điều chỉnh x sao cho nó có một con bổ
sung. (Để chia một nút gốc đầy, đầu tiên chúng ta tạo một nút gốc là một nút
con của một nút gốc mới rỗng để ta có thể sử dụng thủ tục B-TREE-SPLIT-
CHILD). Ý nghĩa của việc chia chỉ là tăng trưởng chiều cao của cây lên 1 đơn
vị.
Hình 18.5 minh họa tiến trình này. Nút đầy y được tách quanh khóa
trung tuyến S, khóa S được di chuyển lên ở nút cha x của y. Những khóa trong
y lớn hơn khóa trung tuyến đều được đặt trong một nút mới z, được tạo làm
một con mới của x.
Hình 18.5 Tiến trình tách một nút có t = 4. Nút y được tách thành hai
nút: y và z và khóa trung tuyến S của y được dời lên vào cha của y.
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
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 12
B-TREES
8 do c
j
[z] – c
j+1
[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)
B-TREE-SPLIT-CHILD hoạt động bằng cách đơn giản "cắt và dán". Ở
đây, y là con thứ i của x và là nút đang được tách. Ban đầu nút y có 2t con (2t
- 1 khóa) nhưng được rút gọn thành t - 1 khóa bởi thao tác này. Nút z “nhận”
nút con lớn nhất t (t - 1 khóa) của y, và z trở thành một con mới của x, được
định vị ngay sau y trong bảng các con của x. Khóa trung tuyến của y dời lên
để trở thành khóa trong nút x tách thành nút y và nút z.
Các dòng 1-8 tạo nút z và cho nó t - 1 khóa lớn hơn và tương ứng với t
nút con của y. Dòng 9 điều chỉnh số khóa của y. Cuối cùng, các 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. Các dòng 17-19 ghi ra tất cả các trang đĩa
được thay đổi. Thời gian chiếm CPU bởi thủ tục B-TREE -SPLIT-CHILD là
)(tΘ
, do các vòng lặp trên các dòng 4-5 và 7-8. (Các vòng lặp khác chạy O(t)
lần lặp lại). Thủ tục này thực hiện O(1) thao tác trên đĩa.
Chèn một khóa vào một B-tree trong một cây đơn hướng xuống
Chúng ta chèn một khóa k vào B-tree T có độ cao h trong một cây đơn
hướng xuống, yêu cầu O(h) lần truy xuất đĩa. Thời gian chiếm CPU cần thiết
là O(th) = O(t log
t
n). Thủ tục B-TREE-INSERT sử dụng thủ tục B-TREE-
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 13
B-TREES
SPLIT-CHILD để đảm bảo rằng việc đệ quy không bao giờ chuyển đến một

nút đầy.
B-TREE -INSERT(T, k)
1 r  root[T]
2 if n[r] = 2t-1
3 then s  ALLOCATE-NODE()
4 root[T]  s
5 leaf[s] FALSE
6 n[s]  0
7 c
i
[s]  r
8 B-TREE -SPLIT-CHILD(s, l, r)
9 B-TREE -INSERT-NONFULL(s, k)
10 Else B-TREE -INSERT-NONFULL(r, k)
Các dòng 3-9 xử lý trường hợp mà ở đó nút gốc r là đầy: nút gốc được
tách và một nút mới s (có hai con) trở thành gốc. Việc tách gốc chỉ là cách để
gia tăng chiều cao của một B-tree. Hình 18.6 minh họa trường hợp này. Khác
với một cây nhị phân tìm kiếm, một B-tree gia tăng chiều cao ở đỉnh thay vì ở
đáy. Thủ tục này hoàn tất bằng cách gọi thủ tục B-TREE-INSERT-
NONFULL để thực hiện việc chèn khóa k trong cây có gốc tại một nút không
đầy. Thủ tục B-TREE-INSERT-NONFULL cần thiết đệ quy hướng xuống
cây ở mọi lúc, và đảm bảo rằng nút mà được gọi đệ quy sẽ không đầy bằng
cách gọi thủ tục B-TREE-SPLIT-CHILD nếu cần.
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 14
B-TREES
Hình 18.6 Tách gốc có t = 4. Nút gốc r được tách thành hai, và một nút
gốc mới s được tạo. Gốc mới chứa khóa trung tuyến của r và có hai nửa của r
làm các con. Chiều cao B-tree tăng lên một khi gốc được tách.
Thủ tục đệ quy bổ trợ B-TREE-INSERT-NONFULL chèn khóa k vào
nút x mà được giả định là không đầy khi thủ tục được gọi. Sự thực thi của thủ

tục B-TREE-INSERT và thao tác đệ quy của thủ tục B-TREE-INSERT-
NONFULL đảm bảo giả định này là đúng.
B-TREE -INSERT-NONFULL(x, k)
1 i  n[x]
2 if leaf[x]
3 then while i
≥
1 và k < key
i
[x]
4 do key
i+1
[x] key
i
[x]
5 i  i-1
6 key
i+1
[x]  k
7 n[x]  n[x]+1
8 DISK-WRITE(x)
9 else while i
≥
1 và k < key
i
[x]
10 do i  i-1
11 i  i + 1
12 DISK-READ(c
i

[x])
13 if n[c
i
[x]] = 2t-1
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 15
B-TREES
14 then B-TREE -SPLIT-CHILD(x, i, c
i
[x])
15 if k > key
i
[x]
16 then i  i+1
17 B-TREE -INSERT-NONFULL (c
i
[x], k)
Thủ tục B-TREE-INSERT-NONFULL làm việc như sau: các dòng 3-8
xử lý trường hợp ở đó x là một nút lá bằng cách chèn khóa k vào x. Nếu x
không phải là một nút lá, thì ta chèn k vào một nút lá thích hợp trong cây con
có gốc tại nút thường x. Trong trường hợp này, các dòng 9-11 xác định con
của x nơi mà lời gọi đệ quy đi xuống. Dòng 13 phát hiện xem việc đệ quy có
đi xuống một con đầy hay không, trong trường hợp đó dòng 14 sử dụng thủ
tục B-TREE-SPLIT-CHILD để tách nút con đó thành hai nút con không đầy,
và các dòng 15-16 xác định con nào trong số hai con lúc vừa tách đúng chính
xác là nút con để đi xuống (Lưu ý rằng một thao tác DISK-READ(c
i
[x])
không cần thiết sau sự tăng i ở dòng 16, vì trong trường hợp này phép đệ quy
sẽ đi xuống một con vừa mới được tạo bởi thủ tục B-TREE-SPLIT-CHILD).
Như vậy, sự tác động chung của các dòng 13-16 đó là đảm bảo thủ tục không

bao giờ đệ quy đến một nút đầy. Sau đó, dòng 17 gọi đệ quy để chèn k vào
cây con thích hợp. Hình 18.7 minh họa nhiều trường hợp khác nhau để chèn
vào một B-tree .
(a) Cây bắt đầu

(b) Chèn B
(c) Chèn Q
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 16
G M P T X
A B C D E Q R S N O U V Y ZJ K
G M P X
A C D E J K R S T U VN O Y Z
G M P X
A B C D E J K R S T U VN O Y Z
B-TREES
d) Chèn L
(e) Chèn F
Hình 18.7: Chèn các khóa vào B-tree. Mức tối thiểu t của B-tree là 3,
vì thế một nút có thể có tối đa là 5 khóa. Các nút được tô màu nhạt bị thay
đổi bởi tiến trình chèn. (a) Cây bắt đầu cho ví dụ này. (b) Kết quả của chèn B
vào cây bắt đầu; đây là một sự chèn đơn giản vào một nút lá. (c) Kết quả của
chèn Q vào cây trước đó. Nút RSTUV được chia thành 2 nút chứa RS và UV,
khóa T được di chuyển lên gốc, và Q được chèn vào góc trái của nửa thứ hai
(nút RS). (d) Kết quả của chèn L vào cây trước đó. Nút gốc được chia ngay
lập tức, vì nó là đầy, và B-tree tăng trưởng một bậc về chiều cao. Sau đó L
được chèn vào lá chứa JK. (e) Kết quả của chèn F vào cây trước đó. Nút
ABCDE được chia trước khi F được chèn vào góc phải của nửa thứ hai (nút
DE).
Số lần truy xuất đĩa được thực hiện bởi thủ tục B-TREE-INSERT là
O(h) đối với một B-tree có chiều cao h, vì chỉ có O(1) thao tác DISK-READ

và DISK-WRITE được thực hiện giữa lời gọi đến thủ tục B-TREE-INSERT-
NONFULL. Tổng thời gian chiếm CPU là O(th) = O(t log
t
n). Vì thủ tục B-
TREE-INSERT-NONFULL là đệ quy cuối, nên nó có thể thực thi lựa chọn
như một vòng lặp while, điều này chứng tỏ rằng số các trang cần thiết ở trong
bộ nhớ chính tại bất cứ thời điểm nào là O(1).
18.3 Xóa một khóa từ một B-tree
Xóa từ B-tree cũng tương tự như chèn nhưng có phần phức tạp hơn, bởi
vì một khóa có thể xóa từ bất cứ nút nào – không chỉ là nút lá. Việc xóa từ
một nút thường đòi hỏi nút con thuộc nó phải được bố trí lại. Giống như việc
chèn, chúng ta phải đề phòng việc xóa một nút của một cây làm vi phạm đến
tính chất của B-tree. Tương tự chúng ta phải đảm bảo một nút khi chèn thì
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 17
P
A B C D E J K L Q R S N O Y Z
G M T X
U V
P
A B J K L Q R S N O Y Z
C G M T X
U VD E F
B-TREES
không quá lớn, đồng thời cũng phải đảm bảo rằng một nút khi xóa thì không
được quá nhỏ (ngoại trừ nút gốc cho phép có ít hơn số tối thiểu t - 1 khóa, dù
nó không cho phép để có nhiều hơn số tối đa 2t - 1 khóa). Một thuật toán chèn
đơn giản phải dự phòng trường hợp một nút là đầy nơi mà khóa được chèn
vào, một cách tiếp cận đơn giản đối với việc xóa đó là phải dự phòng trường
hợp một nút (trừ gốc) có số khóa nhỏ nhất dọc theo đường đi đến nơi khóa bị
xóa.

Giả sử rằng thủ tục B-TREE-DELETE được yêu cầu để xóa khóa k từ
cây con có gốc tại x. Thủ tục này được thiết kế để đảm bảo rằng bất cứ khi
nào thủ tục B-TREE-DELETE được gọi đệ qui trên nút x, số khóa trong x ít
nhất là bằng mức tối thiểu t. Chú ý rằng điều kiện này đòi hỏi nhiều hơn một
khóa so với số tối thiểu đòi hỏi bởi những điều kiện của B-tree thông thường,
vì thế đôi khi một khóa có thể phải di chuyển vào nút con trước khi đệ quy
giảm xuống với nút con đó. Ràng buộc chặt chẽ này cho phép ta xóa một khóa
từ cây theo hướng xuống mà không cần phải “dự phòng” (ngoại trừ một điều
mà chúng ta sẽ giải thích sau). Đặc tả sau đây của việc xóa nút từ B-tree được
giải thích với cách hiểu ở trên đó là nút gốc x trở thành một nút thường không
có khóa (trường hợp này có thể xảy ra ở trường hợp 2c và 3b bên dưới), khi x
bị xóa và nút con duy nhất của x c
1
[x] trở thành gốc mới của cây, chiều dài
của cây suy giảm đi một và duy trì thuộc tính gốc của cây chứa ít nhất một
khóa (trừ cây rỗng).
Chúng ta đã phác thảo cách xóa thay vì đưa ra giải thuật, Hình18.8
minh họa cách xóa các khóa từ B-tree theo những trường hợp khác nhau.
(a) Cây bắt đầu
(b) Xóa F: trường hợp 1
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 18
A B
P
J K L Q R SN O Y Z
C G M T X
U VD E F
P
A B J K L Q R SN O Y Z
C G M T X
U VD E

B-TREES
(c) Xóa M: trường hợp 2a
(d) Xóa G: trường hợp 2c
(e) Xóa D: trường hợp 3b
(e') Cây được rút ngắn lại
(f) Xóa B: trường hợp 3a
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 19
P
A B
J K
Q R SN O Y Z
C G L T X
U VD E
P
A B Q R SN O Y Z
C L T X
U VD E J K
C L P T X
A B Q R SN O U V Y ZE J K
C L P T X
A B Q R SN O U V Y Z
E J K
E L P T X
A C Q R SN O U V Y ZJ K
B-TREES
Hình 18.8: Xóa các khóa từ một B-tree. Mức tối thiểu của B-tree này là
t = 3, vì thế một nút (trừ nút gốc) không thể có ít hơn 2 khóa. Những nút có
thay đổi được tô nhạt. (a) B-tree ở hình 18.7(e). (b) Xóa F Đây là trường hợp
1: xóa đơn giản một nút lá. (c) Xóa M Đây là trường hợp 2a: Nút cha L của
M được di chuyển lên để lấy vị trí của M. (d) Xóa G Đây là trường hợp 2c: G

được đẩy xuống tạo thành nút DEGJK, và sau đó G bị xóa khỏi nút lá này
(trường hợp 1). (e) Xóa D Đây là trường hợp 3b: phép đệ quy không thể giảm
xuống nút CL bởi vì nó chỉ có 2 khóa, vì thế P bị đẩy xuống và kết hợp CL và
TX để tạo thành CLPTX; sau đó, D bị xóa khỏi lá (trường hợp 1). (e') Sau (d)
gốc bị xóa và cây giảm chiều cao của nó đi một. (f) Xóa B Đây là trường hợp
3a: C được di chuyển để điền vào vị trí của B và E được di chuyển để điền
vào vị trí của C.
1. Nếu khóa k trong nút x và x là một lá, xóa khóa k khỏi x.
2. Nếu khóa k trong nút x và x là một nút thường, thực hiện công việc
sau:
a. Nếu nút con y đứng trước khóa k trong nút x có ít nhất t khóa, thì
tìm nút cha k’ của k trong cây con có gốc tại y. Đệ qui để xóa k',
và thay thế k bằng k’ trong x. (Tìm k’ và xóa nó có thể được thực
hiện theo chiều hướng xuống).
b. Một cách đối xứng, nếu con z theo sau k trong nút x có ít nhất t
khóa thì tìm phần tử tiếp theo k’ của k trong cây con mà gốc tại
z. Đệ qui để xóa k’ và thay k bằng k’ trong x (Tìm k' và xóa nó
có thể được thực hiện theo chiều hướng xuống)
c. Mặt khác, nếu cả y và z đều chỉ có t-1 khóa, kết hợp k và tất cả z
vào trong y, để cho x mất cả k và con trỏ trỏ đến z, và y bây giờ
chứa 2t-1 khóa. Sau đó, giải phóng z và đệ qui xóa k từ y.
3. Nếu khóa k không có trong nút thường x, xác định gốc c
i
[x] của cây
con thích hợp chứa k, nếu k là ở trong cây. Nếu c
i
[x] chỉ có t-1 khóa,
thực hiện bước 3a hoặc 3b để đảm bảo rằng ta đang giảm xuống đến
nút chứa ít nhất t khóa. Sau đó hoàn thành bằng việc đệ qui trên nút con
thích hợp của x.

a. Nếu c
i
[x] chỉ có t-1 khóa nhưng có nút anh em có ít nhất t khóa,
cho c
i
[x] một khóa phụ bằng cách di chuyển một khóa từ x xuống
c
i
[x], di chuyển một khóa từ nút anh em bên trái hoặc bên phải
của c
i
[x] đến x
b. Nếu c
i
[x] và cả những nút anh em kế cận của c
i
[x] có t - 1 khóa,
kết hợp c
i
[x] với một nút anh em mà có liên quan đến việc di
chuyển một khóa từ x xuống nút mới được kết hợp để trở thành
khóa trung tuyến cho nút đó.
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 20
B-TREES
Vì hầu hết các khóa trong một B-tree là trong các nút lá, chúng ta có
thể hy vọng rằng trong thực tế, việc xóa thường được sử dụng để xóa các các
từ lá. Thủ tục B-TREE -DELETE thực thi theo một chiều đi xuống xuyên
suốt cây mà không phải quay lại. Tuy nhiên, khi xóa một khóa trong một nút
thường, thủ tục thực hiện đi xuống xuyên suốt cây nhưng có thể quay trở lại
nút mà khóa đã bị xóa để thay đổi khóa với nút cha hoặc nút con của nó

(trường hợp 2a và 2b).
Mặc dù thủ tục này có vẻ như phức tạp, nó chỉ có O(h) các thao tác đĩa
cho một B-tree có chiều cao h, vì chỉ có O(1) các thao tác DISK-READ và
DISK-WRITE được gọi giữa các thủ tục đệ qui. Thời gian CPU yêu cầu là
O(th)=O(t log
t
n).
Vấn đề 18-1: Ngăn xếp trên bộ nhớ thứ cấp
Các thao tác PUSH và POP được hỗ trợ trên các giá trị từ đơn. Với
ngăn xếp, chúng ta mong muốn có thể hỗ trợ lớn hơn nhiều so với dung lượng
bộ nhớ chính, và vì thế hầu như nó phải được lưu trữ trên đĩa.
Một cách đơn giản, nhưng không hiệu quả, sự thực thi ngăn xếp giữ
cho toàn bộ ngăn xếp trên đĩa. Chúng ta duy trì trong bộ nhớ một con trỏ ngăn
xếp, mà đó là địa chỉ của phần tử trên cùng của ngăn xếp. Nếu con trỏ có giá
trị p, phần tử trên cùng là từ thứ (p mod m) trên trang thứ ⌊ p / m ⌋ của đĩa, với
m là số từ trên một trang.
Để thực hiện thao tác PUSH, chúng ta tăng con trỏ ngăn xếp, đọc trang
tương ứng vào bộ nhớ từ đĩa, sao chép phần tử được đẩy vào từ thích hợp trên
trang, và ghi trang trở lại trên đĩa. Tương tự với thao tác POP. Ta giảm con
trỏ ngăn xếp, đọc trang thích hợp từ đĩa, và trả lại đỉnh của ngăn xếp. Chúng
ta không cần phải ghi lại các trang, vì nó không được sửa đổi.
Vì thao tác trên đĩa tương đối tốn chi phí, chúng ta tính hai chi phí cho
bất kỳ sự thực thi nào đó là: tổng số lần truy xuất đĩa và tổng thời gian sử
dụng CPU. Bất kỳ việc truy xuất đĩa nào đến một trang của từ m phải gánh
chịu chi phí của một lần truy xuất đĩa và Θ (m) thời gian sử dụng CPU.
a. Số lần truy xuất đĩa cho n thao tác trên ngăn xếp sử dụng việc thực
hiện đơn giản này là bao nhiêu trong trường hợp xấu nhất? Thời gian CPU
cho n thao tác trên ngăn xếp là bao nhiêu? (Trình bày câu trả lời liên quan đến
m và n cho câu hỏi này và các phần tiếp theo.)
Bây giờ xem như sự thực thi của ngăn xếp mà trong đó ta giữ một trang

của ngăn xếp trong bộ nhớ. (Chúng ta cũng duy trì một dung lượng nhỏ của
bộ nhớ để theo dõi trang hiện thời ở trong bộ nhớ). Chúng ta có thể thực hiện
một thao tác ngăn xếp chỉ nếu trang đĩa tương ứng nằm trong bộ nhớ. Nếu cần
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 21
B-TREES
thiết, trang hiện tại trong bộ nhớ có thể được ghi vào đĩa và trang mới đọc từ
đĩa vào bộ nhớ. Nếu trang đĩa tương ứng đã có trong bộ nhớ, thì không yêu
cầu truy xuất ổ đĩa nữa.
b. Số lần truy xuất ổ đĩa cần thiết cho n thao tác PUSH là bao nhiêu
trong trường hợp xấu nhất? Tính thời gian sử dụng CPU?
c. Số lần truy xuất ổ đĩa cần thiết cho n thao tác trên ngăn xếp là bao
nhiêu trong trường hợp xấu nhất? Tính thời gian sử dụng CPU?
Giả sử rằng bây giờ chúng ta thực hiện ngăn xếp bằng cách giữ hai trang
trong bộ nhớ (thêm vào một số ít từ cho mỗi trang).
d. Hãy mô tả làm thế nào để quản lý các trang của ngăn xếp để giảm
dần số lần truy xuất đĩa cho bất kỳ hoạt động ngăn xếp với O (1 / m) và thời
gian CPU là O (1).
Vấn đề
Thao tác nối lấy từ 2 tập động S’ và S” và một phần tử x mà cho bất kỳ
x'
∈
S ' và x"
∈
S", ta có key[x'] <key [x] <key [x"] . Nó trả về một tập S = S'
∪
{x}
∪
S". Thao tác chia giống như một thao tác nối nghịch đảo: nghĩa là
cho một tập động S và một phần tử x
∈

S, nó tạo ra một tập S' bao gồm tất cả
các phần tử trong tập S – {x} mà có các khóa ít hơn key[x] và một tập S" bao
gồm tất cả các phần tử trong tập S - {x} mà có các khóa lớn hơn key[x]. Trong
vấn đề này, chúng ta khảo sát làm thế nào để thực hiện các thao tác như thế
trong cây 2-3-4. Để thuận tiện, ta giả định rằng các yếu tố chỉ bao gồm các
khóa và tất cả các giá trị của các khóa là khác biệt nhau.
a. Hãy trình bày bằng cách nào nào để đảm bảo với mỗi nút x của một
cây 2-3-4, chiều cao của cây con có gốc tại x chính là trường height[x]. Hãy
chắc chắn rằng việc thực hiện không ảnh hưởng đến thời gian chạy của thao
tác tìm kiếm, chèn, và xóa.
b. Hãy trình bày bằng cách nào để thực hiện các thao tác nối. nếu cho
hai cây 2-3-4 T ' và T và một khóa k, thao tác nối nên thực hiện trong thời
gian O (1 + |h’ - h’’|) , với h’ và h’’ tương ứng với chiều cao của T' và T ".
c. Gọi đường đi P từ gốc của một cây 2-3-4 T đến một khóa k cho
trước, tập S’ chứa các khóa trong cây T mà nhỏ hơn k, và tập S" chứa các
khóa trong cây T mà lớn hơn k. Hãy chỉ ra rằng p phá vỡ tập S ' thành một tập
các cây {T’
0
, T’
1
, , T’
m
} và một tập các khóa {k’
1
, k’
2
, ,k’
m
} trong đó ta có
y<k’

i
<z với i = 1, 2, , m và các khóa y
∈
T’
i-1
, z
∈
T’
i
. Mối quan hệ giữa chiều
cao mỗi cây T’
i-1
và T’
i
là gì? Hãy mô tả cách p phá vỡ S" thành tập các cây
và các khóa như thế.
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 22
B-TREES
d. Hãy trình bày bằng cách nào để thực hiện thao tác tách trên cây T. Sử
dụng thao tác nối để kết hợp các khóa trong tập S’ trong một cây T’ 2-3-4 đơn
và các khóa trong tập S" trong một cây T’’ 2-3-4 đơn. Thời gian thực thi của
hoạt động tách nên là O(lg n), trong đó n là số khóa trong cây T. (Gợi ý: chi
phí cho thao tác nối nên tính vào.)
Chú giải chương
Knuth[185], Aho, Hopcroft và Ullman[5], và Sedgewich[269] đưa ra
những thảo luận sâu hơn của lược đồ cây cân bằng và B-tree. Comer[66] cung
cấp một khảo sát toàn diện của B-tree. Guibas và Sedgewick[135] thảo luận
các mối quan hệ giữa nhiều loại lược đồ cây cân bằng, bao gồm cây đỏ-đen và
cây 2-3-4.
Vào năm 1970, J.E. Hopcroft đề xuất các cây 2-3, một giả mã cho B-

tree và cây 2-3-4, trong đó mỗi nút thường có 2 hoặc 3 con. B-tree được giới
thiệu vởi Bayer và McCreight vào năm 1972[32]; họ không giải thích về tên
gọi của nó.
Bender, Demaine, và Farach-Colton[37] đã nghiên cứu cách để B-tree
thực thi tốt với những ảnh hưởng về cấp bậc bộ nhớ. Những thuật toán đối với
bộ nhớ ẩn của họ làm việc một cách hiệu quả mà không cần biết kích cỡ dữ
liệu được trao đổi bên trong hệ thống bộ nhớ có cấp bậc khác nhau.
Nhóm 7 – Khoa học máy tính Khóa 2009-2011 Trang 23