Explain Indexing in Operating System in detail?

Software Development
#1

The indexed file allocation is somewhat similar to linked file allocation as indexed file allocation also uses pointers but the difference is here all the pointers are put together into one location which is called index block. That means we will get all the locations of blocks in one index file. The blocks and pointers were spread over the memory in the Linked Allocation method, where retrieval was accomplished by visiting each block sequentially. But here in indexed allocation, it becomes easier with the index block to retrieve.

Advantages

  • It reduces the possibilities of external fragmentation.
  • Rather than accessing sequentially it has direct access to the block.

Disadvantages

  • Here more pointer overhead is there.
  • If we lose the index block we cannot access the complete file.
  • It becomes heavy for the small files.
  • It is possible that a single index block cannot keep all the pointers for some large files

To resolve this issue, we can use:

1. Linked Scheme

If the file is big then more blocks are required so one index block is insufficient to store all the pointers, therefore to store the pointers two or more index blocks are used where these index boxes are connected using linked file allocation that is each index block stores the pointer to the next index block.

2. Multilevel Index

In this method, the multiple indexes blocks along with the levels of these blocks. Here, the level 1 block is used for pointing to the level 2 block which points to the blocks occupied by the file. These index blocks can be extended to three or more levels according to the size of the file.

3. Combined Scheme

In Combined Scheme, a special block is used to store all the information related to the file like name, authority, size, etc. The special block is called inode(information-node). Some space of this special block is used to store the information related to the field as mentioned above and the remaining space is used to store the addresses of blocks that contain the actual file.