Indexing (Ch. 9)

Chapter 9

Given this B+ tree where N=5, show the tree after inserting 30.

Given this B+ tree where N=5, show the tree after deleting 14.

Given this B+ tree where N=5, show the tree after inserting 4.

1. access types

2. access time

3. insertion time

4. deletion time

5. space overhead

When creating an index, what are the 5 evaluation metrics we used to determine if the index is ‘good’?

the ordering of the file

Which does the primary index determine when using an ordered index?

yes

In a B+ tree, is the length of the path from the root to any leaf the same?

between ceiling(N/2) and N children

In a B+ tree, an internal node that is not a leaf or the root must have how many children?

sparse index

Which type of index does not require every search-key to appear?

ceiling((N-1)/2) and N-1 values

In a B+ tree, a leaf node that is not the root must have how many values?

bulk loading

What is the process of adding a large number of entries to a B+ tree at one time?

index on A.dogId

Given the following query:

SELECT D.name, D.age FROM dog D, appt A WHERE A.dogId=D.dogId AND A.time=0800;

Which of the following indices could be useful for the query:

1. index D.name

2. index on A.dogId

3. index on D.age

B+ Tree index

Given the following query:

SELECT D.name, D.age FROM dog D, appt A WHERE A.dogId=D.dogId AND D.age>100;

Which of the following indices could be useful for the query for D.age?

1. both B+ Tree and Hash

2. B+ Tree index

3. neither B+ Tree or Hash

4. Hash index

ordered indices and hash indices

What are the two main types of indices?

in a sequentially ordered file, the index whose search key specifies the sequential order of the file

What is a clustering (primary) index?

an index whose search key specifies an order different from the sequential order of the file

What is the non-clustering (secondary) index?

a sequential file ordered on a search key, with a clustering index on the search key

What is an index-sequential file?

when an index appears for every search-key value in the file

What is a dense index?

when a file contains index records for only some search-key values

What is a sparse index?

a sparse index with an index entry for every block in the file, corresponding to last search-key value in the block

What is a good tradeoff for clustered indices?

a sparse index on top of dense index/multilevel index

What is a good trade-off for unclustered indices?

dense

Are secondary indices dense or sparse?

secondary indices

Which type of indices use buckets that contain pointers to all the records?

at least 2

If the root of a B+ tree is not a leaf, how many children must it have?

between 0 and N-1

if the root of a B+ Tree is a leaf, how many values can it have?

a query that finds all records with search-key values in a given range

Define range queries.

ceiling(log_ceiling(N/2)(k))

If there are k search-key values in a file, what is the max height of the tree?

1. Find the leaf node in which the search-key value would appear

2. If there is room in the leaf node, insert the pointer/value pair into the leaf node

3. Otherwise, split the node

List the steps to insert a new value in a B+ Tree.

1. Take the n (search-key value pointer) pairs (including the one being inserted) in sorted order

2. Place the first ceiling(N/2) in the original node, and the rest in a new node

3. Let the new node be p, and let k be the least key value in p. Insert (k,p) in the parent of the node being split

4. If the parent is full, split it and propagate the split further up

List the steps to split a leaf node when inserting a value.

1. Remove the pointer/value pair from the leaf node

2. If the node has too few entries, then merge siblings if enough room

   1. insert all values in the 2 nodes into a single node (left) and delete other node

   2. delete the pointer/value pair (k_i-1, p_i), where p_i is the pointer to the deleted node, from the parent node, recursively using above procedure

3. Otherwise, redistribute pointers

   1. redistribute between node and a sibling such that both have more than the minimum number of entries

   2. update corresponding search-key values in parent

List the steps to delete a value from a leaf node in a B+ Tree.

the root is deleted and the sole child becomes the root

What happens if a root has only one pointer after deletion?

1. merge left

2. merge right

3. borrow left

4. borrow right

When deleting a node from a B+ tree, what are the 4 options in order?