# File Structures (B and B+ Trees)

SEQUENTIAL FILE

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 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

(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.

(a) Indexed sequential access method

(b) B-tree index

(c) B+ tree 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.

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.

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

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.

Second level index is always sparse.

Number of levels = n

Number of blocks = ∑

Number of blocks access = n + 1

leaf nodes are all at same level.

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 ]

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.]

**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] = 1Number 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 childrenleaf 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.]

## No comments