When there is requirement to access records sequentially by some key value and also to access records directly by the similar key value, the collection of records may be organized in an effectual manner called Indexed Sequential Organization.
You have to be familiar with search procedure for a word in a language dictionary. The data into the dictionary is stored in sequential manner. Though, an index is provided in terms of thumb tabs. To search for a word we do not search in sequence. We access the index. That is, locate an approximate location for the word and then proceed to discover the word sequentially.
To implement the concept of indexed sequential file organizations, we assume an approach in which the index part and data part reside on a separate file. The index file has a tree structure and data file has a sequential structure. As the data file is sequenced, it is not essential for the index to have an entry for each record. Assume the sequential file with a two-level index.
Level 1 of the index holds an entry for each three-record section of the main file. The Level 2 indexes Level 1 in the similar way.
While the new records are added in the data file, the sequence of records needs to be preserved and also the index is accordingly updated.
Two approaches used to implement indexes are static indexes and dynamic indexes. As the main data file changes because of insertions and deletions, the contents of the static index may change, however the structure does not change. In case of dynamic indexing approach, insertions and deletions in the main data file may lead to changes in the index structure. Recall the change in height of B-Tree as records are inserted & deleted.
Both dynamic & static indexing techniques are useful based on the type of application.
A directory is a component of file. Consider a file which doesn't have any keys for its records. While a query is executed on such a file, the time consumed to execute the query is more while compared to another file which is having keys, because, there
may be arising obligation where in the file ought to be sorted on the field(s) on which the query is based. Thus, for each query, the file ought to be sorted on the field on which the query is based that is cumbersome. In the case of files which have keys, distinct versions of the files which result because of sorting on the keys are stored in the directory of that file. Such files are called index files and the number of index files varies from file to file. For instance, consider the file of Figure. If we designate Enrolment Number (Enum) and Name as keys, then we might have two index files depends on the each key. Certainly, we can have more than two index files, to deal along with queries which employ both the keys. Different software store index files in a different manner so that the operations on the records can be performed as soon as possible after the query is submitted.
One of the prominent indexing techniques is Cylinder-Surface indexing.
As, there exists a primary key for each of the files, there will be an index file depend on the primary key. Cylinder-Surface Indexing is useful for such index file. In this kind of indexing, the records of the file are stored one after another in such a way that the primary keys of the records are in enhancing order. The index file will have two fields. They are cylinder index & corresponding surface indexes. There will be multiple cylinders and there are multiple surfaces corresponding to each of cylinder. Assume that the file needs m cylinders, then cylinder index will have m entries. Each cylinder will be having one entry that corresponds to the largest key value into that cylinder. Suppose that the disk has n surfaces that can be used. Then, each of surface indexes has n entries. The k-th entry in surface index for cylinder lth cylinder if the value of the largest key on the lth tracks of the kth surface. So, m.n shows the overall number of surface index entries.
Assume that the need arises to search for a record whose key value is B. Then, the primary step is to load the cylinder index of the file into memory. Generally, each cylinder index occupies just one track as the number of cylinders are only few. The cylinder that holds the desired record is found by searching the cylinder index. In general, the search takes O(log m) time. After the search of cylinder index, the equivalent cylinder is determined. Depend on the cylinder, the corresponding surface index is retrieved to look the record for which the search has started. Whenever a search is initiated for the surface index, usually sequential search is used. Of course, it depends on the number of surfaces. But, generally, the number of surfaces is less. After determining the cylinder to be accessed and after finding the surface to be accessed, the corresponding track is loaded into memory and that track is searched for the required record.