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

Methods of collision resolution, Methods of Collision Resolution 1)  Co...

Methods of Collision Resolution 1)  Collision Resolution by separate chaining  2)  Collision Resolution by open addressing

Traversing a graph, two standards ways of traversing a graph in data struc...

two standards ways of traversing a graph in data structure

Declaring a two dimensional array, Declaring a two dimensional array   A...

Declaring a two dimensional array   A two dimensional array is declared same to the way we declare a one-dimensional array except that we state the number of elements in both di

State cmy model, CMY Model  The cyan, magenta, yellow (CMY) colour mode...

CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard

Define abstract data type & column major ordering for arrays, Q1. Define th...

Q1. Define the following terms: (i) Abstract data type. (ii) Column major ordering for arrays. (iii)  Row major ordering for arrays. Q2. Explain the following: (i) A

Tree structure, We would like to implement a 2-4Tree containing distinct in...

We would like to implement a 2-4Tree containing distinct integer keys. This 2-4Tree is defined by the ArrayList Nodes of all the 2-4Nodes in the tree and the special 2-4Node Root w

Numerical - algorithm, Q. What is the smallest value of n such that an algo...

Q. What is the smallest value of n such that an algorithm whose running time is 100n2 runs faster than an algorithm whose running time is 2n on the same machine.    A n

Characterstics of good algorithm, what are the charaterstics to determine w...

what are the charaterstics to determine weather an algorithm is good or not? explain in detail

Explain almost complete binary tree, Almost Complete Binary Tree :-A binary...

Almost Complete Binary Tree :-A binary tree of depth d is an almost whole binary tree if: 1.Any node and at level less than d-1 has two children. 2. for any node and in the tree wi

What is bubble sort, What is bubble sort? Bubble Sort: The basic ide...

What is bubble sort? Bubble Sort: The basic idea in bubble sort is to scan the array to be sorted sequentially various times. Every pass puts the largest element in its corr

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