Classification of Indexing

In the previous page we have seen one classification. Here we are going to discuss one more classification.

Primary Index (Primary Key + Ordered Data) A primary index is an ordered file whose records are fixed length size with 2 fields. First field is same as primary key and the second field is pointer to the data block.


Example on Primary Index

Number of Records = 30000, Block Size = 1024 Bytes, Strategy = Unspanned, Record Size = 100 Bytes,
Key Size = 6 Bytes, Pointer Size = 9 Bytes, Then find average number of block accesses with or without
index.

Data Records that can fit in 1 Block = 1024/100 = 10.24 block but we have to take the whole number so
we have to take only 10 records.
10 records can put in 1 block,
Total records = 30000, so total number of blocks = 30000/10 = 300 Blocks.
So without index we need ceil [log3000] = 12 blocks to access for finding the record. With Index Size of index = 15 Bytes (6+4)
Index Record / Block = floor [1024/15] = 68 [because strategy is unspanned]
Index Records = Number of data blocks = 3000
So no of index blocks = ceil (3000/68) = 45
So average number of block accesses = ceil [log45] + 1 = 6 + 1 = 7


Clustered Indexing

Clustered Index is an ordered file with two fields, non-key and block pointer.
Clustering Index is created on data file whose file records are physically ordered on a non-key field which does not have distinct value for each record, that field is called clustering field.
Explanation
Average Number of block accesses required >= logB + 1

Secondary Index

This a type of dense Index.

Index fields are key (unordered) and block pointer
Example on Secondary Index

Number of Records = 30000, Block Size = 1024 Bytes, Strategy = Unspanned, Record Size = 100 Bytes,
Key Size = 6 Bytes, Pointer Size = 9 Bytes, Then find average number of block accesses with or without
index.

Without Index
To search we need (30000 + 1) / 2 = 15001 Block accesses. With Index Size of index = 15 Bytes (6+4)
Index Record / Block = floor [1024/15] = 68 [because strategy is unspanned]
Index Records = Total Number of Records = 30000 So no of index blocks = ceil (30000/68) = 442
So average number of block accesses = ceil [log442] + 1 =

Example 2

Multi Level Indexing

Data Records = 16384, Size of Record = 32 Bytes, Storage Strategy = Unspanned, Block Size = 1024 Bytes, Size of key = 6 Bytes, Block Pointer = 10 Bytes

Answer:
Index Size = key size + block size = 16 Bytes
Index Records per block = 1024 / 16 = 64
Total Block required = Total record / record per block = 16384 / 64 = 256 This was first level indexing.
Second level Index:
Here we will use sparse index. Number of record = Number of blocks of 1st level index = 256
Number of blocks required = 256 / 64 = 4 Blocks
So to search a record how many blocks will be required = log4 + 1 + 1 = 4 Accesses.

Pictorial Representation

Important Note

Sometimes in the question Block pointer and record pointer are confusing. So choose the one which has larger size as record pointer and other will be Block pointer.


Quantitative Aptitude
Reasoning
Programming
Interview