Indexing in Databases - Set 1 - GeeksforGeeks

1. Single level Index

• Primary Index(Sparse): A primary index is an ordered file(ordered with key field), records of fixed length with two fields. The first field is the same as the primary key of the data file and the second field is a pointer to a data block, where the key is available. In Sparse indexing, for a set of database records there exists a single entry in the index file.

  • Number of index file entries ≤ Number of database records.

• Secondary Index (Dense): Secondary index provides secondary means of accessing a file for which primary access already exists. In Dense indexing, for every database record, there exists an entry in the index file. The index blocking factor is the same for all indexes.

  • Number of database records = Number of entries in the index file

  • Number of block accesses=

    

• Clustered Index(Sparse): A clustering index is created on a data file whose records are physically ordered on a non-key field (called a Clustering field). ****Almost one clustering index is possible.

  • Single-level index blocks=

    

  • Number of block accesses=

    

2. Multilevel Index

• Indexed sequential access method: Second level index is always sparse.

  • Level 1 = “first-level index blocks” computed by index

  • Level 2 =

    

  • Level n =

    

  • Number of blocks =

    

  • Number of block access = n+1

• B-Tree: Also known as Baye’s or balanced Search Tree. At every level, we have Key and Data pointers, and data pointer points either block or record.

  • Root node: B-tree can have children between 2 and p, where p is the Order of the tree.

  • Internal Node:  to n children.

    

  • Leaf nodes all are at the same level.

  • Block size = p × (size of block pointer) + (p-1)× (Size of key field + size of record pointer)

  • Minimum number of nodes =

    

  • Maximum number of nodes = \frac{p^{h+1}-1}{p-1}

  • Minimum height = \left ( \left \lceil log_p \ l \right \rceil \right ) l is the number of leaves

  • Maximum height = \left \lfloor 1 +log_{\frac {p}{2}} \frac{l}{2} \right \rfloor

• B+ Tree: It is the same as B-tree. All the records are available at the leaf (last) level. B tree allows both sequential and random access whereas in B-tree only random access was allowed. Each leaf node has one block pointer and all the leaf nodes are connected to the next leaf node using a block pointer.

  • Order of non-leaf node= [p × size of block pointer] + [(p-1) × size of key field] <= Block size.
  • Order of Leaf node= [(pleaf -1) × (size of key field + size of record pointer) + p × (size of block pointer) <= Block size]