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

Algorithm and flow chart, algorithm and flow chart to find weather the give...

algorithm and flow chart to find weather the given numbers are positive or negative or neutral

Linked list implementation of a dequeue, Double ended queues are implemente...

Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

Complexity classes, Complexity classes All decision problems fall in se...

Complexity classes All decision problems fall in sets of comparable complexity, called as complexity classes. The complexity class P is the set of decision problems which ca

Search, What are the conditions under which sequential search of a list is ...

What are the conditions under which sequential search of a list is preferred over binary search?

Calculate address of an element in an array., Q. Explain the technique to c...

Q. Explain the technique to calculate the address of an element in an array. A  25 × 4  matrix array DATA is stored in memory in 'row-major order'. If base  address is 200 and

Insertion of a key into a b-tree, Example: Insertion of a key 33 into a B-...

Example: Insertion of a key 33 into a B-Tree (w/split) Step 1: Search first node for key closet to 33. Key 30 was determined. Step 2: Node pointed through key 30, is se

Explain decision tree, Decision Tree A decision tree is a diagram that ...

Decision Tree A decision tree is a diagram that shows conditions and actions sequentially and therefore shows which condition is to be considered first, second and so on. It is

Total impedent of the circuit, an electrical student designed a circuit in...

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Stack, Explain the array and linked list implementation of stack

Explain the array and linked list implementation of stack

Exact analysis of insertion sort, Exact analysis of insertion sort: Let...

Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s

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