B-tree C 语言辅导数据结构
- 首页 >> C/C++编程CIS*4430 (Winter 2018): Solutions to Assignment Two
1 (a) (i) (4 marks) Number of records per sector: floor(1024/200) = 5 records/sector
For the file of 8000 records, we need 8000/5 = 1600 sectors.
- The internal sort phase uses all 4 buffers for a run, resulting in 1600/4 = 400 runs:
seek and lantency for each sequential access: 18 + 8.3 = 26.3 msec
total number of sequential read accesses: 400
total seek time for the reading step: 400 seeks x 26.3 msec = 10.52 sec
total data transfer time for the input: 1600 x 1024 / 1229 = 1333.12 msec = 1.33 sec
total time for the reading step: 10.52 + 1.33 = 11.85 sec.
total time for the writing step: 11.85 sec
total I/O access time for the sort phase: 11.85 x 2 = 23.70 sec.
(ii) (4 marks) The merge phase uses 3 buffers for the input, one for each run, saving the 4th
buffer for the output. Thus, we need to do multiple-level 3-way merges.
Pass # Sorted segment length # of sorted segments
---------------------------------------------------------------------------------------------
internal sort 4 sectors 400
merge 1 12 134
merge 2 36 45
merge 3 108 15
merge 4 324 5
merge 5 972 2
merge 6 (2-way will do) 1600 (entire sorted file)
------------------------------------------------------------------------------------------------
Total disk accesses for the entire merge-sort process:
7 passes x (1600 reads + 1600 writes) = 22,400.
(b) (6 marks) Since the file is stored in 1600 sectors, the sparse index will need 1600 distinct
pointers in its bottom, leaf level (level 1).
(i) Number of entries per sector: floor (1024 / (40 + 5)) = 22 entries/sector
level #pointers #sectors
-------------------------------------------------
1 1600 73
2 73 4
3 4 1
--------------------------------------------------
(ii) Number of entries per sector: floor (1024 / (15+5)) = 51 entries/sector
level #pointers #sectors
-------------------------------------------------
1 1600 32
2 32 1
--------------------------------------------------
B-tree implementation:
// pseudocode for “insertion” function
short insert( short rrn, KEY_PTR key, short * promo_rrn, KEY_PTR * promo_key) {
if (rrn == NIL) {
copy “key” to “*promo_key”
set “*promo_rrn” to NILL;
return PROMOTED
}
load “rrn” to “page” and search for “key”
if found return ERROR
short promoted = insert(page.child[found_pos], key, promo_rrn, promo_key);
if (promoted != PROMOTED)
return promoted
if (page.count < MAXKEYS) {
add “promo_key” and “promo_rrn” to “page”
write “page” back to “rrn”
return OKAY
} else {
split “page” into “page” and “new_page” and set “promo_key”
create a new B-tree page and set it to “promo_rrn”
write “page” back to “rrn”
write “new_page” to “promo_rrn”
update the header record for B-tree index
return PROMOTED
}
}