Indexing

Question 1

describe a disk

Answer 1

organised into tracks and sectors

a track in a sector is a block

contiguous blocks are clusters

Question 2

what is an index

Answer 2

allows us to access data elements directly.

stored as a separate table.

points to an address

ordered

Question 3

what is a primary index

Answer 3

primary key

ordered file

fixed length

two fields: key and pointer

Question 4

what is a secondary index

Answer 4

defined on a field of our choosing

Question 5

what is a pointer

Answer 5

points to a location in memory

Question 6

what is an anchor record

Answer 6

the first record in each block of the data file

Question 7

what is a sparse index

Answer 7

has entries for only some of the search values (less than half)

Question 8

is a primary index sparse

Answer 8

yes, it only contains keys of anchors rather than every search value

Question 9

what are the advantages of a sparse index

Answer 9

occupies a smaller space

binary search is faster

more index entries fit on a block

Question 10

what are clustering indexes

Answer 10

records are physically ordered on a nonkey field

speeds up retrieval

Question 11

is a clustering index sparse

Answer 11

depends if nonkey field is unique or not

nonkey so CAN be more than value for the field

one entry in the clustering index for each distinct value

pointer to the first block

Question 12

what are secondary indexes

Answer 12

a means of accessing a data file for which primary access already exists

data doesn’t have to be ordered

created on a candidate or non key field

pointer is either a block or a record pointer

Question 13

is a secondary index dense

Answer 13

yes

Question 14

if we create a secondary index on a candidate key…

Answer 14

it will be unique but unordered so the index will be dense.

The index will create an ordering that allows us to perform binary search

Question 15

if we create a secondary index on a non key field…

Answer 15

there will be duplicates

Question 16

what are our 3 options for dealing with duplicates in a secondary index

Answer 16

1- create duplicate index entries

2- have a variable length index with repeated pointer fields

3- have fixed length index entries and add a layer of indirection

Question 17

how do we perform binary search on a multi level index

Answer 17

considerer the first-level index file as a sorted data file
create a primary index for the first level
create a secondary index to the first level

because secondary index is on the primary key too, we can use pointers to anchors

Question 18

what are B and B+ trees (general)

Answer 18

special cases of trees

Question 19

what is a B tree

Answer 19

an m-way search tree.

each node has multiple indexes and multiple pointers

Question 20

describe a search tree of order p

Answer 20

node contains p-1 search values

and p pointers

Question 21

describe key values that contain pointers

Answer 21

we can also make our key values be pointers to disk

Question 22

what is the rule when deleting from a b tree

Answer 22

if the deletion causes a node to be less than half full, combine with neighbours

Question 23

what is a B+ tree

Answer 23

an implementation of a dynamic multi level index

• data pointers are only stored at leaf nodes
• leaf nodes are linked (base level index)
• internal nodes = other levels in the index

Question 24

what is the difference between B trees and B+ trees

Answer 24

Btrees

• contain pointers at various levels.
• values not repeated

B+trees

• retain middle values to guide the search
• pointers only at leaf nodes creating a sequential linked list