| paulsm4 |
10-06-2005 10:59 PM |
OK, here's a copy of my homework assignment on what I suspect is a similar (the same?) topic from a couple of years ago:
Quote:
Binary searching B-tree blocks for keys is an important for DBMS systems.
The keys are arrays, and are contiguous in the B-tree block.
Lower performance systems, e.g., Oracle, store the keys as arrays of bytes.
Higher performance DBMS systems, e.g. MKF, store the keys as arrays of
longwords: When comparing the target key against a key in the B-tree block,
you must do 4 times as many compares when the keys are arrays of bytes
compared to the case when the keys are arrays of longwords. Therefore, in
this exercise the keys are arrays of longwords. (The most significant
longword is first.)
In a B-tree block, a key is the value of the key column(s) followed by an
address pointer. The address pointer points to a lower level B-tree block,
or to a row in a data block. In this exercise as in MKF, the key arrays are
fixed length.
When you search for a target key, you may or may not find it. If you find
it, you need to find the first duplicate, if there are duplicates.
If you don't find it, you need the index of the point at which you should
insert the target key (after first shifting all the keys from that point
onward up by one key position).
Write a binary search routine to search a B-tree block for a target key that
satisfies the following signature:
FN_uint32_t
binary_search(
FN_uint32_t *a,
FN_int32_t n,
FN_int32_t key_lw,
FN_uint32_t *target_p,
FN_int32_t *index_p);
The array a[] holds the keys. key[i] starts at a[i * key_lw]. The index
of the first key is 0 (and it starts at a[0]), and the index of the last key
is n - 1 (and it starts at a[(n-1) * key_lw]).
n >= 0.
The key_lw parameter is the number of longwords in a key. 1 <= key_lw <= 4.
The target_p parameter points to the first longword of the target key.
If the key is found, 1 is returned, else 0.
If the key is found, *index_p is set to the index of the first key
in the array that has a value identical to the target key (i.e., duplicate
keys are allowed in the array).
If the key is not found, *index_p is set to the insertion point (i.e.,
the index of the key minimally greater than the target key), or, if the target
key is greater than all the keys in the array a[], *index_p is set to 'n'.
Your goal is to write a the fastest B-tree key search routine in the world.
That is, no one can write a faster routine.
The key_lw parameter is the number of longwords (unsigned 32 bit integers)
per key. This value can range from one to four. Your routine should work
for any n >= 0.
Put the binary_search routine in the attached file called "binsearch.c".
Do not create your own file. Edit the attached file.
|
I suppose I could post my solution, verbatim.
But instead, let me ask these questions:
1. What exactly does your "create()" function do?
2. Where exactly does the "option" parameter come from?
... and ...
3. "a[]" is an array of exactly what?
(or, to put it differently: "what exacty is the definition of 'item'?"
Thanx in advance .. PSM |
