XINU Index Blocks

Index blocks are define the sequence of disk blocks that make up each file. The idea of index blocks are that any data block of a file may be found fairly quickly. Lets consider other possible file organizations.

• If the file data blocks were linked in a linear list, then sequential access to the file would be simple and fast, but direct access to a particular block would be very slow in that many disk accesses would have to be performed to find the desired disk (the list would have to be traversed up to that point).
• A contiguous arrangement of data blocks would provide fast and simple sequential and direct access to any part of the file, but growing a file would be difficult in the case that the block following the last for that file was used by another file.

XINU's indexing approach allows simple sequential access, and fairly fast direct access. Since there are 29 pointers to data blocks in a XINU index block, it means that any of the first 29 data blocks can be directly accessed once the first index block is read. Directly accessing any of the next 29 would require reading the second index block, and so on.

UNIX employs a multi-level indexing scheme. In UNIX, pointers to the first 10 data blocks are contained right in the directory entry (called an inode) for that file. The 11th pointer points to an index block which in turn points to the data blocks 11 through 11 + X (where X is the number of disk addresses that can fit in one disk block - it depends on the size of the disk block). The 12th pointer in the directory entry points to doubly-indirected index block which points to a set of index blocks. Each of those index blocks points to a set of data blocks. Finally, the 13th entry of the directory entry for that file points to an index block, which points to a set of index blocks, each of which point to another set of index blocks, each of which point to a set of data blocks. This scheme is shown below. The point is to allow almost arbitrary sized files, with very fast access to the first few blocks (most files are small), and reasonable access to any block.

XINU's scheme is more simple than UNIX's. It also allows arbitrary-sized files, but direct access to the last blocks of a large XINU file will require more disk reads than for those of a similar UNIX file.