CS6400 Exam Prep Questions Solved 100%
Correct | Verified Answers
After the first initial step of building the index is done, we need to sort it
After the sort, the key values we have picked up for the secondary index are all going to come
in order K1, K2, etc. but the pointers are going to point in different directions (not in order)
This makes secondary indexes good for point queries only
Cannot use the pointer to get the next/subsequent key values
Lookup times for secondary index - ✔✔(log2(N) + 1) * page fault time
N is number of index blocks (dense only)
based on the assumption that the nonkey values we are indexing on are unique
Multilevel index - ✔✔Build an index on the index, and an index on the index of the
index, etc., until we end up at the root with just a single index page
Searching through a multilevel index - ✔✔Look at the top level block, knowing it has a
fanout of up to 60
Among those 60 different key values, we pick the place where the key we are searching for
is equal to one of them or fits between two of them, and follow the appropriate pointer to
the next level
, Continue for all levels until at the bottom of the index level and add one in order to get to
the data level
allow us to cut the search space into much smaller pieces in each step
Lookup time for multilevel index - ✔✔(log fanout(N) + 1) * page fault time
the larger the base of the log function is the flatter the log is (for lookup)
Multilevel index -- B+ tree - ✔✔Insertion, deletion, and update operations are
implemented to keep the tree balanced
Only rarely does an overflow at a lower level of the tree propagate more than 1-2 levels up
Static Hashing - ✔✔You have a very large space of key values (for example: Email
addresses of regular users)
Hash function h Job of the hash function is to take keys from the key value space and
match them into an address in a bucket directory
Good hash function properties - ✔✔Distribute values uniformly over the address space
Fill buckets as much as possible because it takes more than just a few blocks, and therefore
needs to be stored somewhere and therefore a piece of it might be stored on disk and itself be
subject to being ported between disk and memory
Avoid collisions -- Collisions occur when the hash function maps the actual keys that occur
to the same space too many times
Correct | Verified Answers
After the first initial step of building the index is done, we need to sort it
After the sort, the key values we have picked up for the secondary index are all going to come
in order K1, K2, etc. but the pointers are going to point in different directions (not in order)
This makes secondary indexes good for point queries only
Cannot use the pointer to get the next/subsequent key values
Lookup times for secondary index - ✔✔(log2(N) + 1) * page fault time
N is number of index blocks (dense only)
based on the assumption that the nonkey values we are indexing on are unique
Multilevel index - ✔✔Build an index on the index, and an index on the index of the
index, etc., until we end up at the root with just a single index page
Searching through a multilevel index - ✔✔Look at the top level block, knowing it has a
fanout of up to 60
Among those 60 different key values, we pick the place where the key we are searching for
is equal to one of them or fits between two of them, and follow the appropriate pointer to
the next level
, Continue for all levels until at the bottom of the index level and add one in order to get to
the data level
allow us to cut the search space into much smaller pieces in each step
Lookup time for multilevel index - ✔✔(log fanout(N) + 1) * page fault time
the larger the base of the log function is the flatter the log is (for lookup)
Multilevel index -- B+ tree - ✔✔Insertion, deletion, and update operations are
implemented to keep the tree balanced
Only rarely does an overflow at a lower level of the tree propagate more than 1-2 levels up
Static Hashing - ✔✔You have a very large space of key values (for example: Email
addresses of regular users)
Hash function h Job of the hash function is to take keys from the key value space and
match them into an address in a bucket directory
Good hash function properties - ✔✔Distribute values uniformly over the address space
Fill buckets as much as possible because it takes more than just a few blocks, and therefore
needs to be stored somewhere and therefore a piece of it might be stored on disk and itself be
subject to being ported between disk and memory
Avoid collisions -- Collisions occur when the hash function maps the actual keys that occur
to the same space too many times
