Indexed sequential file organisation, Data Structure & Algorithms

Assignment Help:

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.


Related Discussions:- Indexed sequential file organisation

Adjacency matrix of an undirected graph, 1) What will call a graph that hav...

1) What will call a graph that have no cycle? 2) Adjacency matrix of an undirected graph is------------- on main diagonal. 3) Represent the following graphs by adjacency matr

Road transport booking system, what algorithms can i use for the above titl...

what algorithms can i use for the above title in my project desing and implmentation of road transport booking system

Algorithm, Write an algorithm for compound interest.

Write an algorithm for compound interest.

Write down the algorithm of quick sort, Write down the algorithm of quick s...

Write down the algorithm of quick sort. An algorithm for quick sort: void quicksort ( int a[ ], int lower, int upper ) {  int i ;  if ( upper > lower ) {   i = split ( a,

Non-recursive implementation of binary tree traversals, As we have seen, as...

As we have seen, as the traversal mechanisms were intrinsically recursive, the implementation was also easy through a recursive procedure. Though, in the case of a non-recursive me

Pest control program, PART- Pest Control Program Prepare a Pest Contro...

PART- Pest Control Program Prepare a Pest Control Program for the facility that will address the management of Rodents, Insects and Birds. Your Pest Control Program should

Indexed sequential file organisation, When there is requirement to access r...

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

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd