DBMS Menu

Indexed Sequential Access Methods



Indexed Sequential Access Method (ISAM) is a file organization technique that provides efficient ways to both sequentially and randomly access records. In ISAM, data is stored in sorted order based on a key, and an index is maintained to facilitate quick search operations. Originally, it was developed for disk storage but has also been adapted for other storage mediums.

The primary advantage of ISAM is that it combines the benefits of both sequential and direct-access (or random-access) file systems. ISAM structures are often implemented in database management systems to support fast data retrieval and insertion operations.

Components of ISAM

  1. Data File: The records in the data file are stored in sorted order based on a key field.
  2. Index File: The index file contains index entries, which are pointers to blocks (or records) in the data file. These index entries are also sorted based on the key.
  3. Overflow Area: This is used to store new records that are inserted but cannot fit into the primary data area. The overflow area is also organized in a sorted manner.

Working Mechanism of ISAM

  1. Searching: When searching for a record, the system first looks in the index to find the disk block that contains the record. Then, that specific block is fetched to retrieve the record. This usually takes two disk I/O operations.
  2. Insertion: If a new record needs to be inserted, it is placed in its correct sorted position. If the block is full, the record is placed in the overflow area.
  3. Deletion: Deleting a record involves marking it as deleted. The space is then reclaimed during a subsequent reorganization of the data file.
  4. Updating: Updating a record involves either modifying it if the key is not changed, or deleting and re-inserting it if the key is modified.

Example of ISAM

Let's consider a simplified library database where we have a file containing book information sorted by ISBN numbers.

Data File

| ISBN  | Title              |
|-------|--------------------|
| 123   | Book A             |
| 234   | Book B             |
| 345   | Book C             |
| 456   | Book D             |
Index File

| ISBN  | Block Address  |
|-------|----------------|
| 123   | 1              |
| 234   | 2              |
| 345   | 3              |
| 456   | 4              |
Overflow Area

(Initially Empty)

Searching for ISBN 345

  • Search in the index for ISBN 345, and find that it is located at block 3.
  • Go to block 3 in the data file to retrieve the record for ISBN 345 ("Book C").

Inserting a new book with ISBN 133

  • The new book would ideally go into block position 1 (between ISBN 123 and 234).
  • Since the block is full, the new record with ISBN 133 ("New Book") will go into the overflow area.
  • An index entry for ISBN 133 pointing to the overflow area is added.

Updated Overflow Area

| ISBN  | Title     |
|-------|-----------|
| 133   | New Book  |

ISAM provides a reasonable compromise between efficient use of disk space and fast retrieval time. However, it's worth noting that modern databases often use more sophisticated indexing methods like B-trees and B+ trees, which generalize and extend the capabilities of ISAM.

Next Topic :Dynamic Index Structure - B+ Tree