Databases Test 5

Concept:

Indexing is a data structure technique to efficiently retrieve records from database files based on some attributes on which the indexing has been done. It is used to optimize the performance of database.

Explanation:

The index structure typically provides secondary access path i.e. alternate way of accessing the records without affecting the physical placement of records on disk.

There are several types of ordered indexes. A primary index is specified on the ordering key field of an ordered file of records. If ordering field is non key then it is known as clustering index. Non key and ordered means if numerous records in the file can have the same value for ordering field. Clustering index is also known as non-dense index.

Clustering index is an ordered file with two fields:

• First field is of same type as clustering of data file
• Second field is a block pointer.

Concept:

Blocking factor: Number of records that can be stored in one block. It is calculated by dividing the block size by the length of each record.

Calculation:

Block size = 1024 bytes

Number of records = 30000

Record length or size = 100 bytes

File records are of fixed size and unspanned.

So, blocking factor = 1024/ 100 = ⌊10.24⌋ = 10

To find number of blocks needed:

10 records require = 1 block

1 record requires = 1/ 10 block

Data:

Minimum number of keys = MIN = 10

order of a B+ tree = p

Formula:

MIN = ⌈p ÷ 2⌉ – 1

Maximum number of keys = MAX = p – 1

Calculation:

10 = ⌈p ÷ 2⌉ – 1  

∴ p = 21 or p = 22

If p = 21

MAX = 21 – 1 = 20

If p = 22

MAX = p – 1 = 22 – 1 = 21

Data:

Block size = 8192 bytes = 2¹³ bytes

Key size = 32 byte

Block pointer = 4 byte

Order of the b-tree = M

Number of keys = M – 1 

Formula:

In a B-Tree, the size of non-leaf node = M × (Block pointer) + (M – 1) × (key + Record pointer)

Calculation:

Assuming Record pointer = 0  (since nothing is mentioned about it)

Total size = M(4) + (M - 1)(32) = 36 M - 32

Both the given statements are true.

In a sparse index, an index entry appears for only some of the search-key values. Sparse indices can be used only if the relation is stored in sorted order of the search key, that is, if the index is a clustering index. 

It is generally faster to locate a record if we have a dense index rather than a sparse index. However, sparse indices have advantages over dense indices in that they require less space and they impose less maintenance overhead for insertions and deletions. 

Block size = 1024 bytes

Data records =  24000

Index record size = 8 bytes + 7 bytes = 15 bytes

Number of index records per block = 1024/10 = 103

Number of data blocks = 24000/103 = 234

Total number of index records per block = 1024/15 = 69 

Therefore, number of index blocks = Total number of index records/Number of index records per block = 234/69 = 3.39 = 4

Therefore, number of accesses = (log₂4) + 1 = 2 + 1 = 3