www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntuh
UNIT – V
Data on External Storage, File Organization and Indexing, Cluster Indexes, Primary and Secondary Indexes, Index data
Structures, Hash Based Indexing, Tree base Indexing, Comparison of File Organizations, Indexes and Performance Tuning,
Intuitions for tree Indexes, Indexed Sequential Access Methods (ISAM), B+ Trees: A Dynamic Index Structure.
1. DATA ON EXTERNAL STORAGE
Primary memory has limited storage capacity and is volatile. To overcome this limitation,
secondary memory is also termed as external storage devices are used. External storage devices
such as disks and tapes are used to store data permanently.
The Secondary storage devices can be fixed or removable. Fixed Storage device is an
internal storage device like hard disk that is fixed inside the computer. Storage devices that are
portable and can be taken outside the computer are termed as removable storage devices such as
CD, DVD, external hard disk, etc.
Magnetic/optical Disk: It supports random and sequential access. It takes less access time.
Magnetic Tapes: It supports only sequential access. It takes more access time.
In DBMS, processing a query and getting output need accessing random pages. So, disks
are preferable than magnetic tapes.
2. FILE ORGANIZATION
The database is stored as a collection of files. Each file contains a set of records. Each record
is a collection of fields. For example, a student table (or file) contains many records and each
record belongs to one student with fields (attributes) such as Name, Date of birth, class,
department, address, etc.
File organization defines how file records are mapped onto disk blocks.
The records of a file are stored in the disk blocks because a block is the unit of data transfer
between disk and memory. When the block size is larger than the record size, each block will
contain more than one record. Sometimes, some of the files may have large records that cannot
fit in one block. In this case, we can store part of a record on one block and the rest on another. A
pointer at the end of the first block points to the block containing the remainder of the record.
The different types of file organization are given below:
Prepared by: Ravindar Mogili, Associate Professor, JITS-KNR Page: 1
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntuh
, www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntuh
Heap File Sequential File
Organization Organization
File
Organization
Hash File Clustered File
Organization Organization
Heap File Organization: When a file is created using Heap File Organization mechanism, the
records are stored in the file in the order in which they are inserted. So the new records are
inserted at the end of the file. In this type of organization inserting new records is more efficient.
It uses linear search to search records.
Sequential File Organization: When a file is created using Sequential File Organization
mechanism, all the records are ordered (sorted) as per the primary key value and placed in the
file. In this type of organization inserting new records is more difficult because the records need
to be sorted after inserting every new record. It uses binary search to search records.
Hash File Organization: When a file is created using Hash File Organization mechanism, a
hash function is applied on some field of the records to calculate hash value. Based on the hash
value, the corresponding record is placed in the file.
Clustered File Organization: Clustered file organization is not considered good for large
databases. In this mechanism, related records from one or more relations are kept in a same disk
block, that is, the ordering of records is not based on primary key or search key.
3. INDEXING
If the records in the file are in sorted order, then searching will become very fast. But, in
most of the cases, records are placed in the file in the order in which they are inserted, so new
records are inserted at the end of the file. It indicates, the records are not in sorted order. In
order to make searching faster in the files with unsorted records, indexing is used.
Indexing is a data structure technique which allows you to quickly retrieve records from a
database file. An Index is a small table having only two columns. The first column contains a
copy of the primary or candidate key of a table. The second column contains a set of disk block
addresses where the record with that specific key value stored.
Prepared by: Ravindar Mogili, Associate Professor, JITS-KNR Page: 2
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntuh
, www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntuh
Indexing in DBMS can be of the following types:
Indexing
Primary Indexing Secondary Indexing Clustering Indexing
Dense Indexing Sparse Indexing
i. Primary Index
If the index is created by using the primary key of the table, then it is known as primary
indexing.
As primary keys are unique and are stored in a sorted manner, the performance of the
searching operation is quite efficient.
The primary index can be classified into two types: dense index and sparse index.
Dense index
If every record in the table has one index entry in the index table, then it is called dense
index.
In this, the number of records (rows) in the index table is same as the number of records
(rows) in the main table.
As every record has one index entry, searching becomes faster.
TS TS Hyderabad KCR
AP AP Amaravathi Jagan
TN TN Madras Palani Swamy
MH MH Bombay Thackray
Sparse index
If only few records in the table have index entries in the index table, then it is called
sparse index.
In this, the number of records (rows) in the index table is less than the number of records
(rows) in the main table.
As not all the record have index entries, searching becomes slow for records that does not
have index entries.
Prepared by: Ravindar Mogili, Associate Professor, JITS-KNR Page: 3
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntuh
UNIT – V
Data on External Storage, File Organization and Indexing, Cluster Indexes, Primary and Secondary Indexes, Index data
Structures, Hash Based Indexing, Tree base Indexing, Comparison of File Organizations, Indexes and Performance Tuning,
Intuitions for tree Indexes, Indexed Sequential Access Methods (ISAM), B+ Trees: A Dynamic Index Structure.
1. DATA ON EXTERNAL STORAGE
Primary memory has limited storage capacity and is volatile. To overcome this limitation,
secondary memory is also termed as external storage devices are used. External storage devices
such as disks and tapes are used to store data permanently.
The Secondary storage devices can be fixed or removable. Fixed Storage device is an
internal storage device like hard disk that is fixed inside the computer. Storage devices that are
portable and can be taken outside the computer are termed as removable storage devices such as
CD, DVD, external hard disk, etc.
Magnetic/optical Disk: It supports random and sequential access. It takes less access time.
Magnetic Tapes: It supports only sequential access. It takes more access time.
In DBMS, processing a query and getting output need accessing random pages. So, disks
are preferable than magnetic tapes.
2. FILE ORGANIZATION
The database is stored as a collection of files. Each file contains a set of records. Each record
is a collection of fields. For example, a student table (or file) contains many records and each
record belongs to one student with fields (attributes) such as Name, Date of birth, class,
department, address, etc.
File organization defines how file records are mapped onto disk blocks.
The records of a file are stored in the disk blocks because a block is the unit of data transfer
between disk and memory. When the block size is larger than the record size, each block will
contain more than one record. Sometimes, some of the files may have large records that cannot
fit in one block. In this case, we can store part of a record on one block and the rest on another. A
pointer at the end of the first block points to the block containing the remainder of the record.
The different types of file organization are given below:
Prepared by: Ravindar Mogili, Associate Professor, JITS-KNR Page: 1
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntuh
, www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntuh
Heap File Sequential File
Organization Organization
File
Organization
Hash File Clustered File
Organization Organization
Heap File Organization: When a file is created using Heap File Organization mechanism, the
records are stored in the file in the order in which they are inserted. So the new records are
inserted at the end of the file. In this type of organization inserting new records is more efficient.
It uses linear search to search records.
Sequential File Organization: When a file is created using Sequential File Organization
mechanism, all the records are ordered (sorted) as per the primary key value and placed in the
file. In this type of organization inserting new records is more difficult because the records need
to be sorted after inserting every new record. It uses binary search to search records.
Hash File Organization: When a file is created using Hash File Organization mechanism, a
hash function is applied on some field of the records to calculate hash value. Based on the hash
value, the corresponding record is placed in the file.
Clustered File Organization: Clustered file organization is not considered good for large
databases. In this mechanism, related records from one or more relations are kept in a same disk
block, that is, the ordering of records is not based on primary key or search key.
3. INDEXING
If the records in the file are in sorted order, then searching will become very fast. But, in
most of the cases, records are placed in the file in the order in which they are inserted, so new
records are inserted at the end of the file. It indicates, the records are not in sorted order. In
order to make searching faster in the files with unsorted records, indexing is used.
Indexing is a data structure technique which allows you to quickly retrieve records from a
database file. An Index is a small table having only two columns. The first column contains a
copy of the primary or candidate key of a table. The second column contains a set of disk block
addresses where the record with that specific key value stored.
Prepared by: Ravindar Mogili, Associate Professor, JITS-KNR Page: 2
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntuh
, www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntuh
Indexing in DBMS can be of the following types:
Indexing
Primary Indexing Secondary Indexing Clustering Indexing
Dense Indexing Sparse Indexing
i. Primary Index
If the index is created by using the primary key of the table, then it is known as primary
indexing.
As primary keys are unique and are stored in a sorted manner, the performance of the
searching operation is quite efficient.
The primary index can be classified into two types: dense index and sparse index.
Dense index
If every record in the table has one index entry in the index table, then it is called dense
index.
In this, the number of records (rows) in the index table is same as the number of records
(rows) in the main table.
As every record has one index entry, searching becomes faster.
TS TS Hyderabad KCR
AP AP Amaravathi Jagan
TN TN Madras Palani Swamy
MH MH Bombay Thackray
Sparse index
If only few records in the table have index entries in the index table, then it is called
sparse index.
In this, the number of records (rows) in the index table is less than the number of records
(rows) in the main table.
As not all the record have index entries, searching becomes slow for records that does not
have index entries.
Prepared by: Ravindar Mogili, Associate Professor, JITS-KNR Page: 3
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntuh
