Indexing can be classified into two parts as
1)Single Level Index: this is again divides into three parts :
a)Primary index :(PK +Ordered) A primary index is an ordered file whose records of fixed length with two fields. The first field is same as primary key (PK)of data file and the second is a pointer to a data block, where the key is avialable.
- index created for the first record of each block called 'block anchors'.
- The no. of index entries equal to no of data blocks.
- The average no of block access using index=log2 Bi +1 where Bi is block number.
b)Clustered Index: (NK+Ordered) Clustering index is created on the data file whose file record are physically ordered on non key(NK) field which does not have distinct value for each record, that field is called as clustering field.
1. The average no of block access using index=log2 Bi +1 where Bi is block number.
c)Secondary Index(NK/CK + Un-Ordered) Along with primary index if you have one more index then problem is ,that perticular index will not be in sorted order it means that it is unordered , So it is called secomdary index.
here we can say primary indexing is usefull when the search is based on the primary key.
If you have many search request which are based on something else other than primary key then it is better to make index for that particular key also.
- Secondary index may be a non key or candidate key
- Index entry is created for each for each ecord in a data file
- no of index entries = no of record
2)Multi Level Index: here we have B tree and B+tree
you can think B tree and B+ tree as multilevel index means we can insert the nodes ,delete the node and change the level dynamically.
we have two pointer for storing the file and they are:
1)Node pointer or block pointer
we may have a doubt that,why we use B-tree and B+-tree instead of Avl or R B tree and many more?
Reason for this doubt can be understand as, Avl tree or Red black tree they grow in vertically while In B and B+tree ,you can keep the height smaller and we can store as much as data as possible
Using B,B+ tree we reduced the level therefore we reduce the time complexity.