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

Insertion into a red-black tree, The insertion procedure in a red-black tre...

The insertion procedure in a red-black tree is similar to a binary search tree i.e., the insertion proceeds in a similar manner but after insertion of nodes x into the tree T, we c

Stack, write pseudocode to implement a queue with two stacks

write pseudocode to implement a queue with two stacks

Explain linked list and its types, Data Structure and Algorithm 1. Exp...

Data Structure and Algorithm 1. Explain linked list and its types. How do you represent linked list in memory? 2. List and elucidate the types of binary tree. 3. Descr

Determine the greatest common divisor, Determine the greatest common diviso...

Determine the greatest common divisor (GCD) of two integers, m & n. The algorithm for GCD might be defined as follows: While m is greater than zero: If n is greater than m, s

Conversion of general trees to binary trees, Taking a suitable example expl...

Taking a suitable example explains how a general tree can be shown as a Binary Tree. Conversion of general trees to binary trees: A general tree can be changed into an equiv

Hash tables, Q. Explain the Hash Tables, Hash function and Hashing Techniqu...

Q. Explain the Hash Tables, Hash function and Hashing Techniques properly?             A n s . H as h Table is explained as follows : A hash table is a data struc

Applications of shortest path algorithms, The minimum cost spanning tree ha...

The minimum cost spanning tree has broad applications in distinct fields. It represents several complicated real world problems such as: 1. Minimum distance for travelling all o

Hotel reservation system, pls i want a psuedo code for hotel reservation sy...

pls i want a psuedo code for hotel reservation system.

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

How to write binary search algorithm?, Q. Write down the binary search algo...

Q. Write down the binary search algorithm and trace to search element 91 in following given list: 13          30          62           73         81         88             91

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