Find - block search

Hello everyone , To understand the complete static lookup, take a look at the previous article

1.3  Search in blocks

If the index order table represents the static lookup table , You can use block search to realize . Block search is also called index order search . In this search method, besides the table itself, an index table needs to be established .

• 
  
  Construction process

As shown in the figure , The construction process of this table is : Divide the table to be searched into several sub tables with equal length  ( It's called a block ). Create an index entry for each sub table , It includes two items : Keyword item ( Store the largest keyword in the block ) Pointer term ( The address where the first record in the block is stored ). The keywords in the index table are incremented in order , The records in the table can be orderly , It can also be disorderly . But the blocks must be in order ( That is, the minimum keywords in the latter block are greater than the maximum keywords in the previous block ).

• 
  
  Lookup process

The search process is divided into two steps : First, determine the block of the record to be checked in the index table ; then , Find in order in the block . Because the keywords in the index table are incremented orderly , And it is sequential storage, which can be searched in half . The records in the block can only be searched in sequence . therefore , The block search algorithm is a simple synthesis of the above two algorithms .

• 
  
  Average search length

The average search length of block search is  ASL= Lь+Lw.

（ among Lb To determine the average search length of the block where the record to be checked is located ,Lw Is the average search length in the block .）

• 
  
  Find the block in order , Then the average search length of block search is ：

ASLbs = Lь+ Lw= (b+1)/2+ (s+1)/2=(n/s+s)/2+1.

The length will be n The table is evenly divided into b block , Each piece contains s A record , namely b=n/s; It is also assumed that the search probability of each record in the table is the same , That is, the probability of finding each block is 1/b, The search probability of each record in the block is 1/s.

• Half search to determine the block , Then the average search length of block search is :

ASL≈log2 (n/s+1)+s/2

among n Is the length of the table ;s Is the number of records in each block .