Data Structure and Algorithm Using Java
Table of Content
• AIM
* Sequential and Direct Access (Relative Files),
* Index Sequential,
* Indexed Files - B+ Tree as Index, Multi-Indexed Files,
* Inverted Files,
* Hashed Files
CHAPTER 5
File Structures
What is File?
File is a collection of records related to each other. The file size is limited by the size of
memory and storage
medium.
File Organization
File organization ensures that records are available for processing. It is used to determine
an efficient file organization for each base relation.
For example, if we want to retrieve employee records in alphabetical order of name. Sorting
the file by employee name is a good file organization.
However, if we want to retrieve all employees whose marks are in a certain range, a file is
ordered by employee name would not be a good file organization.
Types of File Organization
There are three types of organizing the file:
1. Sequential access file organization
2. Direct access (Relative) file organization
3. Index Sequential,
4. Indexed Files - B+ Tree as Index, Multi-Indexed Files,
5. Inverted Files,
6. Hashed Files
1. Sequential access file organization
• Storing and sorting in contiguous block within files on tape or disk is called as
sequential access file organization.
• In sequential access file organization, all records are stored in a sequential order.
The records are arranged in
the ascending or descending order of a key field.
• Sequential file search starts from the beginning of the file and the records can
be added at the end of the file.
• In sequential file, it is not possible to add a record in the middle of the file
without rewriting the file.
Sequential access file
organization
Advantages of sequential file
• It is simple to program and easy to design.
• Sequential file is best use if storage space.
Disadvantages of sequential file
• Sequential file is time consuming process.
• It has high data redundancy.
• Random searching is not possible.
Direct access file
organization
• Direct access file is also known as random access or relative file organization.
• In direct access file, all records are stored in direct access storage device
(DASD), such as hard disk.
• The records are randomly placed throughout the file.
• The records does not need to be in sequence because they are updated directly
and rewritten back in the
same location.
• This file organization is useful for immediate access to large amount of
information. It is used in accessing
large databases.
• It is also called as hashing.
Direct access file
organization
Advantages of direct access file organization
• Direct access file helps in online transaction processing system (OLTP) like online
railway reservation system.
• In direct access file, sorting of the records are not required.
• It accesses the desired records immediately.
• It updates several files quickly.
• It has better control over record allocation.
Disadvantages of direct access file organization
• Direct access file does not provide back up facility.
• It is expensive.
• It has less storage space as compared to sequential file.
Indexed sequential access
file organization
• Indexed sequential access file combines both sequential file and direct access file
organization.
• In indexed sequential access file, records are stored randomly on a direct access
device such as magnetic disk by a primary key.
• This file have multiple keys. These keys can be alphanumeric in which the records
are ordered is called primary key.
• The data can be access either sequentially or randomly using the index. The index is
stored in a file and read into memory when the file is opened.
Indexed sequential access
file organization
Advantages of Indexed sequential access file organization
• In indexed sequential access file, sequential file and random file access is possible.
• It accesses the records very fast if the index table is properly organized.
• The records can be inserted in the middle of the file.
• It provides quick access for sequential and direct processing.
• It reduces the degree of the sequential search.
Disadvantages of Indexed sequential access file organization
• Indexed sequential access file requires unique keys and periodic reorganization.
• Indexed sequential access file takes longer time to search the index for the data access
or retrieval.
• It requires more storage space.
• It is expensive because it requires special software.
• It is less efficient in the use of storage space as compared to other file organizations.
Indexed sequential access
method (ISAM)
ISAM method is an advanced sequential file organization. In this method, records
are stored in the file using the primary key.
An index value is generated for each primary key and mapped with the record. This
index contains the address of the record in
the file.
Indexed sequential access
method (ISAM)
If any record has to be retrieved based on its index value, then the address of the
data block is fetched and the record is retrieved from the memory.
Pros of ISAM:
o In this method, each record has the address of its data block, searching a record
in a huge database is quick and easy.
o This method supports range retrieval and partial retrieval of records. Since the
index is based on the primary key values,
o we can retrieve the data for the given range of value. In the same way, the partial
value can also be easily searched, i.e., the student name starting with 'JA' can be
easily searched.
Cons of ISAM
o This method requires extra space in the disk to store the index value.
o When the new records are inserted, then these files have to be reconstructed to
maintain the sequence.
o When the record is deleted, then the space used by it needs to be released.
Otherwise, the performance of the database will slow down.
B+ File Organization
o B+ tree file organization is the advanced method of an indexed sequential access
method. It uses a tree-like structure to
store records in File.
o It uses the same concept of key-index where the primary key is used to sort the
records. For each primary key, the
value of the index is generated and mapped with the record.
o The B+ tree is similar to a binary search tree (BST), but it can have more than
two children. In this method, all the
records are stored only at the leaf node. Intermediate nodes act as a pointer to the
leaf nodes. They do not contain any
records.
B+ File Organization
This B+ tree shows that:
o There is one root node of the
tree, i.e., 25.
o There is an intermediary
layer with nodes. They do not
store the actual record. They
have only pointers to the leaf
node.
o The nodes to the left of the
root node contain the prior
value of the root and nodes to
the right contain next value of
the root, i.e., 15 and 30
respectively.
B+ File Organization
o There is only one leaf node which has only values, i.e., 10, 12, 17, 20, 24, 27 and 29.
o Searching for any record is easier as all the leaf nodes are balanced.
o In this method, searching any record can be traversed through the single path and
accessed easily.
Pros of B+ tree file organization
o In this method, searching becomes very easy as all the records are stored only in the
leaf nodes and sorted the sequential linked list.
o Traversing through the tree structure is easier and faster.
o The size of the B+ tree has no restrictions, so the number of records can increase or
decrease and the B+ tree structure can also grow or shrink.
o It is a balanced tree structure, and any insert/update/delete does not affect the
performance of tree.
Cons of B+ tree file organization
o This method is inefficient for the static method.
Inverted Files
An Inverted file is an index data structure that maps
content to its location within a database file, in a
document or in a set of documents. It is normally
composed of: (i) a vocabulary that contains all the
distinct words found in a text and (ii), for each word t of
the vocabulary, a list that contains statistics about the
occurrences of t in the text. Such list is known as the
inverted list of t. The inverted file is the most popular
data structure used in document retrieval systems to
support full text search.
Inverted Files
Hash File Organization
Hash File Organization uses the computation of hash function on some fields of the
records. The hash function's output
determines the location of disk block where the records are to be placed.
Hash File Organization
When a record has to be received using the hash key columns, then the address is
generated, and the whole record is retrieved
using that address. In the same way, when a new record has to be inserted, then the
address is generated using the hash key
and record is directly inserted. The same process is applied in the case of delete and
update.
In this method, there is no effort for searching and sorting the entire file. In this
method, each record will be stored randomly in
the memory.
Hash File Organization