1
Kỹ thuậtlậptrình
Chương 4 – Các cấutrúc
dữ liệutiêntiến
1. Tìm kiếm ngoài – B-cây
(Kruse, Chương 11.3)
1.1. Định nghĩa
Lưutrữ ngoài
 Cho đến nay, ta luôn giảđịnh là có thể lưu
trữ toàn bộ
mộtcấutrúcdữ liệutrongbộ nhớ
trong
 Nếudữ liệulàquálớn không thể vừavớibộ
nhớ trong?
 Æ Sử dụng bộ nhớ ngoài
 Vấn đề: đánh giá độ phứctạpvề thờigiansử
dụng O-lớngiảđịnh mọi thao tác có thờigian
như nhau.
 Æ Không thể áp dụng với thao tác truy cập đĩa
Thờigiantruycập
 Giả sửđĩa quay vớitốc độ: 3600 RPM
 Æ một vòng quay: 1/60 giây = 16.7ms
 Trung bình cầnnửa vòng/truy cập= 8ms
 Æ 1 giây = 120 lầntruycập = 25 triệulệnh
 1 phép truy cập đĩa = 200,000 lệnh
Thờigiantruycập
 Thờigiantruycập:
 Bộ nhớ trong: μs
 Đĩacứng: ms
 Đĩamềm: s
 Đọc file:

 Mục đích:
 có chiềucaonhỏ nhất
 Điềukiện:
 Không có cây con rỗng
 Các nút lá cùng mức
 Có ít nhất m/2 con
Để xây dựng cây có chiềucaonhỏ nhất:
 Đảmbảo sao cho 0 có cây con rỗng xuấthiệntrên
B-cây: Định nghĩa
 Là cây tìm kiếmm-đường:
 Tấtcả nútlácócùngmức
 Nút giữa(trừ nút gốc) có: từđến m nút
con
 Số khóa của nút giữa= số con - 1,
 Các khóa củanútgiữaphânhoạch các khóa của
cây con như cây tìm kiếm
 Nút gốchoặc là nút lá hoặccótừ 2 đến m con
 Nút lá chứa không nhiềuhơn m -1 khóa
⎡⎤
2/m
Nên chọnm lẻ
Ví dụ: B-cây cấp5
3
Ví dụ: B-cây cấp5
1.2. Thao tác thêm
Thêm phầntử vào B-cây
1. Tìm khóa cần thêm
2. Nếu không tìm thấy, thêm khóa vào nút lá tại
vị trí kết thúc
3. Nếu nút lá đầy:

LớpB_tree
template <class Record, int order>
struct B_node {
// data members:
int count;
Record data[order − 1];
B_node<Record, order> *branch[order];
// constructor:
B_node( );
};
Giảithuật tìm kiếm
template <class Record, int order>
Error_code B_tree<Record, order> ::
search_tree(Record &target)
/* Post: If there is an entry in the B-tree whose key
matches that in target, the parameter target is
replaced by the corresponding Record from the
B-tree and a code of success is returned.
Otherwise a code of not_present is returned.
Uses: recursive_search_tree */
{
return recursive_search_tree(root, target);
}
5
recursive_search_tree
template <class Record, int order>
Error_code B_tree<Record, order> :: recursive_search_tree
(B_node<Record, order> *current, Record &target)
/* Pre: current is either NULL or points to a subtree of
the B_tree.

Record is copied to target. Otherwise, a code of not_present is
returned,
and position is set to the branch index on which to continue the
search.
Uses: Methods of class Record. */
search_node
 {
 position = 0;
 while (position < current->count && target > current-
>data[position])
 position ; // Perform a sequential search through the keys.
 if (position < current->count && target == current->data[position])
 return success;
 else
 return not_present;
 }
1.3. Cài đặtgiảithuậtthêm
Thao tác thêm
 Đệ quy
 Tham số:
 Đầuvào:
 new_entry – bản ghi cần thêm
 Đầura:
 current: gốccủa cây con hiệntại
 median: bản ghi trung vị
 right_branch: con trỏ tớinútnửaphảimới
6
Khi một nút bị tách insert
template <class Record, int order>
Error_code B_tree<Record, order> :: insert(const

B_node<Record, order> *current,
const Record &new_entry,
Record &median,
B_node<Record, order> * &right_branch)
/* Pre: current is either NULL or points to a node of a B_tree.
Post: If an entry with a Key matching that of new_entry is in the subtree to
which current points, a code of duplicate_error is returned. Otherwise,
new_entry is inserted into the subtree: If this causes the height of the
subtree to grow, a code of overflow is returned, and the Record median is
extracted to be reinserted higher in the B-tree, together with the subtree
right_branch on its right. If the height does not grow, a code of success is
returned.
Uses: Functions push_down (called recursively), search_node, split_node, and
push_in. */
{
Error_code result;
int position;
if (current == NULL) {
// Since we cannot insert in an empty tree, the recursion terminates.
median = new_entry;
right_branch = NULL;
result = overflow;
}
else { // Search the current node.
if (search_node(current, new_entry, position) == success)
result = duplicate_error;
else {
Record extra_entry;
B_node<Record, order> *extra_branch;
result = push_down(current->branch[position], new_entry,

current->branch[i . 1] = current->branch[i];
}
current->data[position] = entry;
current->branch[position . 1] = right_branch;
current->count ;
}
Tách đôi nút
template <class Record, int order>
void B_tree<Record, order> :: split_node(
B_node<Record, order> *current,// node to be split
const Record &extra_entry, // new entry to insert
B_node<Record, order> *extra_branch, // subtree on right of extra_entr
y
int position, // index in node where extra_entry goes
B_node<Record, order> * &right_half, // new node for right half of entrie
s
Record &median) // median entry (in neither half)
/* Pre: current points to a node of a B_tree. The node *current is full, but if there
were room, the record extra_entry with its right-hand pointer extra_branch
would belong in *current at position position, 0 position < order.
Post: The node *current with extra_entry and pointer extra_branch at positio
n
position are divided into nodes *current and *right_half separated by a Recor
d
median.
Uses: Methods of struct B_node, function push_in. */
{
right_half = new B_node<Record, order>;
int mid = order/2; // The entries from mid on will go to right_half.
if (position <= mid) { // First case: extra_entry belongs in left half.

Xóa median, dịch branch
9
1.3. Xóa nút trên B-cây
Giảithuật
 Phầntử xóa nằm ở nút lá:
 Nútlácósố phầntử > tốithiểu: xóa
 Nútlácósố phầntử = tốithiểu: xét nút lá anh em
kề
 Nếu nút kề có số phầntử > tốithiểu: chuyển1 phầntử
lên nút cha, chuyểnphầntửởnút cha xuống nút lá có
phầntử xóa.
 Nếu nút kề có số phầntử = tốithiểu: phốihợp nút lá,
nút kề và phầntử trung vị tại nút cha thành nút mới.
 Nếu nút cha bị có quá ít phầntử Æ lan truyền lên trên.
 Nút xóa nằmtại nút gốc, cây giảmchiềucao.

Phầntử xóa nằm ở nút giữa:
ÆPhầntử kế tụcnằmtạimột nút lá: thay thế phần
tử kế tụcvớiphầntử xóa => xóa tạinútlá.
Ví dụ Xóa p
Xóa d Phốihợp(tiếp)
10
Kếtquả