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