What are the advantages of indexed-sequential file
organisation? With the help of an example explain the structure of
indexed-sequential file
Ans
Advantage of index sequential file organization:
1. In indexed sequential file organization, the item in the
table can be examined sequentially if all the records in the file must be
accessed.
2. Indexed sequential file organization is very useful when a
random access or records by specifying the key is required.
3. Updating is easily accommodated.
4. Random access is possible.
Given an indexed sequential file
called MASTER which contains records each made up of a key and a set of
information items, this algorithm accesses a record directly and performs the
desired transaction on this record. The cylinder index CYL_INDEX, is considered
to be a vector P in length in which each element contains the two items CYLNO
(Cylinder number) and KEY. The transaction record is referenced using the
variable TRAN_REC which is composed of the items TRANS, KEY,
and INFO.
1. [Initialise]
open MASTER
file for update
read TRAN_REC
2.
[examine cylinder index]
CYLßCYLNO
of CYL_INDEX [P]
Repeat
for I=1, 2, ……., p-1
If
KEY of TRAN_REC<=KEY of CYL_INDEX [I]
Then
CYLßCYLNO of CYL_INDEX [I]
Exit
loop
3.
[examine track index for CYL]
repeat for
j=1,2, . . . . , m
if KEY
or TRAN_REC<=OVFLOW_KEY of TRK_INDEX[ j]
then if
KEY of TRAN_REC<=NORMAL_KEY of TRK_INDEX[ j]
then ADDRßNORMAL_ADDR
of TRK_INDEX[ j]
(ADDR
is initially pointing at the first record on the first
record on
the prime track)
If
TRANS=’ADD’
Then
call IS_PRIME_INSERT (ADDR)
Exit
Repeat
while KEY of PRIME_REC (ADDR)<
KEY
of TRAN_REC
ADDRßbeginning
of next prime track record
Else if
KEY of PRIME_REC (ADDR)! =KEY of TRAN_REC
Then
write (Transaction key does not match, A file key)
Exit
ADDRßOVFLOW_ADDR
of TRK_INDEX[ j]
(ADDR
is initially pointing to first record in list of
Overflow
records)
If
TRANS=’ADD’
Then
call IS_OF_INSERT (ADDR)
Exit
Repeat
while KEY of OVFLOW_REC (ADDR)<
KEY
of TRAN_REC
ADDRßLINK
of OVFLOW_REC (ADDR)
If
KEY of OVFLOW_REC (ADDR)! = KEY
of
TRAN_REC
Then
write (Transaction key does not match, A file key)
Exit
Read
track record at ADDR from MASTER file into MTR_REC
If
TRANS of TRAN_REC=’DELETE”
Then
delete track record at ADDR from MASTER file
Exit
If
TRANS of TRAN_REC=’ALTER’
Then
Rewrite track record at ADDR in MASTER file
With
KEY and INFO of TRAN_REC
Exit
Write
(‘ Illegal transaction specified’)
Exit
4. [Compare keys and change CYL_INDEX
if necessary]
If
TRANS=’ADD’
Then KEY
of CYLN_INDEX [P]ßKEY of TRAN_REC
Call
IS_OF_INSERT (ADDR)
Exit
Else write
(‘Illegal transaction’)
Exit
To implement the concept of indexed sequential file
organizations, we consider 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. Since the data file is sequenced, it is not
necessary for the index to have an entry for each record Following figure shows
a 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 same way.
When the new records are inserted in the data file, the
sequence of records need 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 due to insertions and
deletions, the static index contents may change but 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 and deleted.
Both dynamic and static
indexing techniques are useful depending on the type of application
No comments:
Post a Comment