in Databases edited by
1,794 views
3 votes
3 votes

 

in Databases edited by
by
1.8k views

4 Comments

@srestha

See Mam :

 

Suppose i have a records as shown but the records when stored in file are stored using the  FIRST attribute (The numbers here :) )

Now if i want to do indexing on Name attribute i cant do sparse why ? because as u can see above records are stored using numbers (orderly as both are ordered index) so if i search for 142 i can simply create a sparse index on blocks <Search Key , Block Pointer > and i can do a binary search to go to the record entry <= 142 from there i can do linear scan easily.

But here we are doing indexing on Name attribute imagine i want to search for 'Bart' can i do similar binary search on Sparse index record file (if i do sparse indexing on Name ) to go to 'Bart' , NO ? Why because even if i scan lexicographically, you can see that name follows very different order.

Hence its must to do indexing on every record.

That's why its secondary index as its giving the order of records different from one stored in the files.

So Dense indexing :

I will keep an index corresponding to every Record :

                                     * In one index record i will keep <Search Key , Record Pointer> as You can see above  so size                                         of one entry = 8 + 2 = 10 ( Record pointer + Search Key here its SSN)

                                     * Now how many such entries i can have in a block : 1024/10 = 102, means in one block i can                                           store 102 record index. We need to store for 10,000 records = 10000/102 = 98.02 = 99 blocks

                                     * Now if i again do indexing it will be Sparse , NOTE : Always the first level is sparse or                                                 dense and after then every indexing is sparse Why ? Because now we have blocks to                                           deal with because we have already converted every thing to blocks :)

Had it been Sparse:

As you can see in figure they converted first in blocks, ALWAYS REMEMBER THAT SPARSE INDEX IS ONE PER BLOCK.

Hence Number of blocks to store entire records :- 

How many records i can store in one block = 1024/100 = 10

I have total 10,000 records so 10000/10 = 1000 blocks

 

Now in sparse index file as you can see i store <Search key , Block pointer > (Here block pointer pointing to block and also contains offset within the block to record > , So size of one entry = 6 + 2 = 8 (Block pointer , Search Key)

How many index i can have = 1024/8 = 128 

Hence number of blocks on first level = 1000/128 = 78.

 

Hope you get now MAM

 

2
2
Nice explanation sir.
0
0
Block size = 1024 B

Size of index = 8 + 2 = 10 B.

Number of indices in a block = 1024/10 = 102.

Since in secondary indexing there will be a index for each data record in the database file.It’s dense indexing. Therefore number of indices in  first level = number of data records = 10000.

So, number of blocks in first level = total number of indices/ number of indices in a single block.

number of block in first level = 10000/102 = 98.039.

Since 98 block is sufficient so we will take 99 blocks.
1
1

1 Answer

0 votes
0 votes
Can Indexing be spanned or unspanned ? By default do we take unspanned? If it's not mentioned in the question?