File Structures (B and B+ Trees)

SEQUENTIAL FILE

Blocking factor := [ Block size / Record size ]

Number of record blocks := [ Total no. of records / Blocking factor ]

Average number of blocks accessed by linear search := [ # of record blocks / 2 ]

Average number of blocks accessed by binary search := [ log2 # of record blocks ]

INDEX FILE

Index blocking factor = [ # of record blocks + 1 / 2 ]

First (single) level index blocks := [ # of record blocks / index blocking factor ]

Number of block accesses = [ log2 (first level index blocks)] + 1

Indexing Types

1. Single level Index :
    (a) Primary index ( sparse) : Ordered with key field.
    (b) clustered index (sparse) : Ordered with non key field.
    (c) Secondary index (dense) : Ordered with either key or non key field.

2. Multilevel Index :
    (a) Indexed sequential access  method
    (b) B-tree index
    (c) B+ tree index

SINGLE LEVEL INDEX

Dense Index 
  For every data base record there exists entry in the index file.
  Number of data base records = Number of entries of the index file.



Sparse Index 
  For set of database records there exists single entry in the index files.
  Number of index file entries < Number of database records.
  Number of index files entries = Number of database blocks.

Clustered Index
  Search key should be used to physically order the DB.
  Search key is non-key.
  At most one clustering index is possible.
  Single level index blocks : [ No. of distinct values over non key  field / Index blocking factor] + 1.
  Number of block accesses : [ log2 ( single level index blocks)] + 1

Secondary Index
  Search key is used to non ordered the DB file.
  Search key is primary or alternative key.
  Dense indexing is used.
  Number of block accesses  [ log2 ( single level index blocks)] + 1
  Index blocking factor same for all indexes.

MULTILEVEL INDEX ( STATIC LEVEL INDEX)

Second level index is always sparse.
 Level 1 = "first level index blocks" computed by index.
 Level 2 = [ # of blocks in level (1) / index blocking factor]
 Level n = [ # of blocks in level (n-1) / index blocking factor] = 1
 Number of levels = n
 Number of blocks = ∑ i= 1 to n ( Number of blocks in level i)
 Number of blocks access = n + 1

B-TREE ( BINARY'S/ BALANCED SEARCH TREE)

    Root node : 2 to n children (pointers)
    Internal node : [n/2] to n children
    leaf nodes are all at same level.
    Block Size = p ⤫ ( Size of block pointer) +   (p-1) ⤫ ( Size of key field + size of record pointer)
    Minimum number of nodes = 1+ [2[(p/2)h -1] / (p/2) -2
    Maximum number of nodes = ph+1 - 1 / p-1
    Minimum possible height = [ logp ℓ ]   (ℓ : no. of leaves)
    Maximum possible height = [ 1+ log p/2    ℓ/2 ]

B+ TREE

    It is same as B-tree
    All the records are available at leaf ( last ) level.
    It allows both random and sequential access , but in B-tree only random access allowed.
    All the leaf nodes are connected to next leaf node by block pointers [ every leaf node has one block pointer].
    Order of non-leaf Node:
             [ p⤫ size of block pointer ] + [(p-1) ⤫ size of key field ] =< Block size.
    Order of Leaf Node :
           [ ( p -1) ⤫ (size of key field + size of record pointer) + p ⤫ (size of block pointer) =< Block size.]