UNIT-3

DATA STORAGE AND QUERY PROCESSING

Record storage and Primary file organization- Secondary
storage Devices- Operations on Files- Heap File- Sorted Files-
Hashing Techniques – Index Structure for files –Different types
of Indexes- B-Tree - B+ Tree – Query Processing.

MISSION VISION CORE VALUES

CHRIST is a nurturing ground for an individual’s Excellence and Service Faith in God | Moral Uprightness
holistic development to make effective contribution to Love of Fellow Beings
the society in a dynamic environment Social Responsibility | Pursuit of Excellence
 CHRIST
Deemed to be University
Physical Storage Media
○ Cache
○ Main memory
○ Flash memory
○ Magnetic-disk storage
○ Optical storage Storage device hierarchy
○ Tape storage

The various storage media can be organized in a

hierarchy according to their speed and their cost. The
higher levels are expensive, but are fast. As we move
down the hierarchy, the cost per bit decreases,
whereas the access time increases.

Excellence and Service

 CHRIST
Deemed to be University

Magnetic Disks

Excellence and Service

 CHRIST
Deemed to be University

Excellence and Service

 CHRIST
Deemed to be University

1. Hard Disk Drive (HDD)

● The HDD is an older, mechanical technology.

● Data Storage: Data is stored magnetically on a stack of circular, rigid discs
called platters.
● Data Access: An actuator arm with a read/write head moves across the
spinning platters to locate and retrieve data.
● Limitation: The speed is physically limited by how fast the platters can spin
(usually 5400 or 7200 Revolutions Per Minute, or RPM) and how quickly the
arm can move to the correct location. This results in latency.

Excellence and Service

 CHRIST
Deemed to be University

2. Solid State Drive (SSD)

● The SSD is a modern, electronic technology.

● Data Storage: Data is stored electrically in blocks on NAND flash memory
chips (integrated circuits).
● Data Access: A central controller instantly accesses any memory cell,
similar to how RAM works.
● Advantage: Since there is no physical movement required, data access is
nearly instantaneous, resulting in drastically lower latency and much higher
transfer speeds.

Excellence and Service

 CHRIST
Deemed to be University

Excellence and Service

 CHRIST
Deemed to be University

Use Case Recommendation Why?

Provides the fastest boot-up,
Primary/Boot Drive SSD system responsiveness, and
application loading times.
Drastically reduces game load
Gaming SSD
times (maps, levels, textures).
Essential for fast read/write
Video Editing/CAD SSD speeds when working with large
project files and rendering.
Most cost-effective way to store
terabytes of photos, videos, and
Bulk Storage/Backups HDD
archives that are not accessed
frequently.
Better battery life, silent
operation, and high resistance to
Laptops/Portables SSD
physical damage from being
moved around.

Excellence and Service

 CHRIST
Deemed to be University

Disk Subsystem

● Checksum
● Remapping of bad sectors

Excellence and Service

 CHRIST
Deemed to be University

Performance Measures of Disks

● Access time is the time from when a read or write request is issued to when data transfer
begins.
● The time for repositioning the arm is called the seek time, and it increases with the distance
that the arm must move. Typical seek times range from 2 to 30 milliseconds,
● average seek time is the average of the seek times, measured over a sequence of (uniformly
distributed) random requests.
● the time spent waiting for the sector to be accessed to appear under the head is called the
rotational latency time.
● The average latency time of the disk is one-half the time for a full rotation of the disk.
● The data-transfer rate is the rate at which data can be retrieved from or stored to the disk.
● mean time to failure (MTTF) is a measure of the reliability of the disk. It is the amount of time
that, on average, we can expect the system to run continuously without any failure.

Excellence and Service

 CHRIST
Deemed to be University

Optimization of Disk-Block Access

● Scheduling.
○ Disk-arm–scheduling algorithms
○ Elevator algorithm
● File organization
● Nonvolatile write buffers
● Log disk

Excellence and Service

 CHRIST
Deemed to be University

RAID

● redundant arrays of independent disks (RAID), to achieve improved

performance and reliability.

● Improvement of Reliability via Redundancy

● The simplest (but most expensive) approach to introducing redundancy is to
duplicate every disk. This technique is called mirroring

● Mean time to repair, which is the time it takes (on an average) to replace a
failed disk and to restore the data on it.

Excellence and Service

 CHRIST
Deemed to be University

RAID Levels

Excellence and Service

 CHRIST
Deemed to be University

● The factors to be taken into account when choosing a RAID level are
○ Monetary cost of extra disk storage requirements
○ Performance requirements in terms of number of I/O operations
○ Performance when a disk has failed
○ Performance during rebuild (that is, while the data in a failed disk is being rebuilt on a
new disk)

Excellence and Service

 CHRIST
Deemed to be University

File Organization

● A file is organized logically as a sequence of records. These records are

mapped onto disk blocks.

Excellence and Service

 CHRIST
Deemed to be University

Two types of records stored in a file

● There are different ways of storing data in the database. Storing data in files is one of them. A user can
store the data in files in an organized manner. These files are organized logically as a sequence of records
and reside permanently on disks.
● Each file is divided into fixed-length storage units known as Blocks. These blocks are the units of storage
allocation as well as data transfer. Although the default block size in the database is 4 to 8 kilobytes, many
databases allow specifying the size at the time of creating the database instance.
● Usually, the record size is smaller than the block size. But, for large data items such as images, the size
can vary.
● For accessing the data quickly, it is required that one complete record should reside in one block only. It
should not be partially divided between one or two blocks.
● In RDBMS, the size of tuples varies in different relations. Thus, we need to structure our files in multiple
lengths for implementing the records. In file organization, there are two possible ways of representing the
records:
○ Fixed-length records
○ Variable-length records

Excellence and Service

 CHRIST
Deemed to be University

Fixed-Length Records
● Fixed-length records means setting a length and storing the records
into the file. If the record size exceeds the fixed size, it gets divided
into more than one block.
● Consider the following example

● The customer record is stored in blocks of consecutive storage locations.

E.g.: word or byte
● Each record occupies 40 bytes of memory

● Insertion and Deletion of a record is difficult

Excellence and Service

 CHRIST
Deemed to be University

● At the beginning of the file, a certain number of bytes is allocated as a file header. The file
header stores the address of the first record whose contents are deleted. The first record to
store the address of the second available record, and so on.
● The deleted records thus form a linked list, which is often referred to as a free list.
● On insertion of a new record, the record pointed to by the header is used. The header pointer
is changed to point to the next available record. If no space is available, the new record is
added to the end of the file. This process is similar to pointers.

Insertion and Deletion becomes easy

Excellence and Service

 CHRIST
Deemed to be University

Variable-Length Records
● Consider the following example:

● Variable-length records are the records that vary in size. It requires the creation of multiple
blocks of multiple sizes to store them. These variable-length records are kept in the following
ways in the database system:
○ Storage of multiple record types in a file
○ Record types that allow variable lengths for one or more fields
○ Record types that allow repeating fields

Excellence and Service

 CHRIST
Deemed to be University

● In variable-length records, there exist the following two problems:

○ Defining the way of representing a single record so as to extract the individual attributes
easily.
○ Defining the way of storing variable-length records within a block so as to extract that
record in a block easily.

● These problems can be solved by the following methods:

○ Byte-String Representation
○ Fixed-Length Representation

Excellence and Service

 CHRIST
Deemed to be University

Byte-String Representation
● A simple method for implementing variable-length records is to attach a special
endof-record (⊥) symbol to the end of each record. We can then store each record as
a string of consecutive bytes.

● It is not easy to reuse space occupied formerly by a deleted record.

● There is no space, in general, for records to grow longer. If a variable-length record
becomes longer, it must be moved—movement is costly if pointers to the record are
stored elsewhere in the database (e.g., in indices, or in other records), since the
pointers must be located and updated.
Excellence and Service
 CHRIST
Deemed to be University

slotted-page structure
● It is an alternative form of byte-string representation and is commonly used
for organizing records within a single block.

● There is a header at the beginning of each block, containing the following

information:
1. The number of record entries in the header
2. The end of free space in the block
3. An array whose entries contain the location and size of each record

Excellence and Service

 CHRIST
Deemed to be University

● The actual records are allocated contiguously in the block, starting from the end of the block.
The free space in the block is contiguous, between the final entry in the header array, and the
first record. If a record is inserted, space is allocated for it at the end of free space, and an
entry containing its size and location is added to the header.
● If a record is deleted, the space that it occupies is freed, and its entry is set to deleted (its size
is set to −1, for example). Further, the records in the block before the deleted record are
moved, so that the free space created by the deletion gets occupied, and all free space is
again between the final entry in the header array and the first record. The end-of-free-space
pointer in the header is appropriately updated as well.
● Records can be grown or shrunk by similar techniques, as long as there is space in the block.
The cost of moving the records is not too high, since the size of a block is limited: A typical
value is 4 kilobytes.
● The slotted-page structure requires that there be no pointers that point directly to records.
Instead, pointers must point to the entry in the header that contains the actual location of the
record. This level of indirection allows records to be moved to prevent fragmentation of space
inside a block, while supporting indirect pointers to the record.

Excellence and Service

 CHRIST
Deemed to be University

Fixed-Length Representation

● Another way to implement variable-length records efficiently in a file system is

to use one or more fixed-length records to represent one variable-length
record.
● This can be done by two ways:
○ Reserved space.
○ List representation

Excellence and Service

 CHRIST
Deemed to be University

Reserved space.

● If there is a maximum record length that is never exceeded, we can use fixed-
length records of that length. Unused space (for records shorter than the
maximum space) is filled with a special null, or end-of-record, symbol.
Figure shows how the file would be represented if we allowed a maximum
of three accounts per branch. A record in this file is of the account-list
type, but with the array containing exactly
three elements. Those branches with fewer than three accounts (for
example, Round Hill) have records with null fields. We use the symbol ⊥
to represent this situation in Figure 11.12. In practice, a particular value
that can never represent real data is used (for example, an account
number that is blank, or a name beginning with “*”).
The reserved-space method is useful when most records have a length
close to the maximum. Otherwise, a significant amount of space may be
wasted. In our bank example, some branches may have many more
accounts than others.

● If we choose to apply the reserved-space method to our account example, we

need to select a maximum record length.

Excellence and Service

 CHRIST
Deemed to be University

List representation
● We can represent variable-length records by lists of fixed length records, chained together by pointers.
● A disadvantage to the structure is that we waste space in all records except the first in a chain. The first
record needs to have the branch-name value, but subsequent records do not. Nevertheless, we need to
include a field for branch-name in all records, lest the records not be of fixed length. This wasted space is
significant, since we expect, in practice, that each branch has a large number of accounts.

● To deal with this problem, we allow two kinds of blocks in our file:
1. Anchor block, which contains the first record of a chain
2. Overflow block, which contains records other than those that are the first record of a chain
● Thus, all records within a block have the same length, even though not all records in the file have the same
length.

Excellence and Service

 CHRIST
Deemed to be University

Excellence and Service

 CHRIST
Deemed to be University

Organization of Records in Files

● Heap file organization

● Sequential file organization
● Hashing file organization
● Cluster File Organization
● Indexed sequential access method
● B+ File Organization

Excellence and Service

 CHRIST
Deemed to be University
Heap file organization
● Any record can be placed anywhere in the file where there is space for the record. There is no ordering of
records. Typically, there is a single file for each relation.
● It is the simplest and most basic type of organization. It works with data blocks. In heap file organization,
the records are inserted at the file's end. When the records are inserted, it doesn't require the sorting and
ordering of records.
● When the data block is full, the new record is stored in some other block. This new data block need not to
be the very next data block, but it can select any data block in the memory to store new records. The heap
file is also known as an unordered file.
● In the file, every record has a unique id, and every page in a file is of the same size. It is the DBMS
responsibility to store and manage the new records.

Excellence and Service

 CHRIST
Deemed to be University

● Pros of Heap file organization

○ It is a very good method of file organization for bulk insertion. If there is a large number of
data which needs to load into the database at a time, then this method is best suited.
○ In case of a small database, fetching and retrieving of records is faster than the
sequential record.
● Cons of Heap file organization
○ This method is inefficient for the large database because it takes time to search or modify
the record.
○ This method is inefficient for large databases.

Excellence and Service

 CHRIST
Deemed to be University
Sequential file organization
● This method is the easiest method for file organization. In this method, files are stored
sequentially. This method can be implemented in two ways:
1. Pile File Method
2. Sorted File Method
● Pros of sequential file organization
○ It contains a fast and efficient method for the huge amount of data.
○ In this method, files can be easily stored in cheaper storage mechanism like magnetic
tapes.
○ It is simple in design. It requires no much effort to store the data.
○ This method is used when most of the records have to be accessed like grade
calculation of a student, generating the salary slip, etc.
○ This method is used for report generation or statistical calculations.
● Cons of sequential file organization
○ It will waste time as we cannot jump on a particular record that is required but we have to
move sequentially which takes our time.
○ Sorted file method takes more time and space for sorting the records.

Excellence and Service

 CHRIST
Deemed to be University
Pile File Method
● It is a quite simple method. In this method, we store the record in a sequence, i.e., one after
another. Here, the record will be inserted in the order in which they are inserted into tables.
● In case of updating or deleting of any record, the record will be searched in the memory
blocks. When it is found, then it will be marked for deleting, and the new record is inserted.

● Insertion of the new record:

○ Suppose we have four records R1, R3 and so on upto R9 and R8 in a sequence. Hence, records are
nothing but a row in the table. Suppose we want to insert a new record R2 in the sequence, then it
will be placed at the end of the file. Here, records are nothing but a row in any table.

Excellence and Service

 CHRIST
Deemed to be University
Sorted File Method
● In this method, the new record is always inserted at the file's end, and then it will sort the sequence in ascending or
descending order. Sorting of records is based on any primary key or any other key.
● In the case of modification of any record, it will update the record and then sort the file, and lastly, the updated record is
placed in the right place.

● Insertion of the new record:

○ Suppose there is a preexisting sorted sequence of four records R1, R3 and so on upto R6 and R7. Suppose a new
record R2 has to be inserted in the sequence, then it will be inserted at the end of the file, and then it will sort the
sequence.

Excellence and Service

 CHRIST
Deemed to be University

Hashing 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.

Excellence and Service

 CHRIST
Deemed to be University

● 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.

Excellence and Service

 CHRIST
Deemed to be University
clustering file organization
● When the two or more records are stored in the same file, it is known as clusters. These files
will have two or more tables in the same data block, and key attributes which are used to map
these tables together are stored only once.
● This method reduces the cost of searching for various records in different files.
● The cluster file organization is used when there is a frequent need for joining the tables with
the same condition. These joins will give only a few records from both tables. In the given
example, we are retrieving the record for only particular departments. This method can't be
used to retrieve the record for the entire department.

● In this method, we can directly insert, update or delete any record. Data is sorted based on the
key with which searching is done. Cluster key is a type of key with which joining of the table is
performed.
Excellence and Service
 CHRIST
Deemed to be University

Types of Cluster file organization

1. Indexed Clusters:
○ In indexed cluster, records are grouped based on the cluster key and stored together.
The above EMPLOYEE and DEPARTMENT relationship is an example of an indexed
cluster. Here, all the records are grouped based on the cluster key- DEP_ID and all the
records are grouped.
2. Hash Clusters:
○ It is similar to the indexed cluster. In hash cluster, instead of storing the records based on
the cluster key, we generate the value of the hash key for the cluster key and store the
records with the same hash key value.

Excellence and Service

 CHRIST
Deemed to be University

● Pros of Cluster file organization

○ The cluster file organization is used when there is a frequent request for joining the
tables with same joining condition.
○ It provides the efficient result when there is a 1:M mapping between the tables.
● Cons of Cluster file organization
○ This method has the low performance for the very large database.
○ If there is any change in joining condition, then this method cannot use. If we change the
condition of joining then traversing the file takes a lot of time.
○ This method is not suitable for a table with a 1:1 condition.

Excellence and Service

 CHRIST
Deemed to be University

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.

● 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.
Excellence and Service
 CHRIST
Deemed to be University

● Pros of ISAM:
○ In this method, each record has the address of its data block, searching a record in a
huge database is quick and easy.
○ This method supports range retrieval and partial retrieval of records. Since the index is
based on the primary key values, 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
○ This method requires extra space in the disk to store the index value.
○ When the new records are inserted, then these files have to be reconstructed to maintain
the sequence.
○ When the record is deleted, then the space used by it needs to be released. Otherwise,
the performance of the database will slow down.

Excellence and Service

 CHRIST
Deemed to be University

B+ File Organization
● 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.
● 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.
● 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.
• There is one root node of the tree, i.e., 25.
• There is an intermediary layer with nodes.
They do not store the actual record. They
have only pointers to the leaf node.
• 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.
• There is only one leaf node which has only
values, i.e., 10, 12, 17, 20, 24, 27 and 29.
• Searching for any record is easier as all the
leaf nodes are balanced.
• In this method, searching any record can be
traversed through the single path and
accessed easily.

Excellence and Service

 CHRIST
Deemed to be University

● Pros of B+ tree file organization

○ In this method, searching becomes very easy as all the records are stored only in the leaf
nodes and sorted the sequential linked list.
○ Traversing through the tree structure is easier and faster.
○ 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.
○ It is a balanced tree structure, and any insert/update/delete does not affect the
performance of tree.
● Cons of B+ tree file organization
○ This method is inefficient for the static method.

Excellence and Service

 CHRIST
Deemed to be University
Indexing in DBMS
● Indexing is used to optimize the performance of a database by minimizing the
number of disk accesses required when a query is processed.
● The index is a type of data structure. It is used to locate and access the data in a
database table quickly.

● Indexes can be created using some database columns.

● The first column of the database is the search key that contains a copy of the primary
key or candidate key of the table. The values of the primary key are stored in sorted
order so that the corresponding data can be accessed easily.
● The second column of the database is the data reference. It contains a set of pointers
holding the address of the disk block where the value of the particular key can be
found.
Excellence and Service
 CHRIST
Deemed to be University

Indexing Methods

Excellence and Service

 CHRIST
Deemed to be University

Ordered Indices

● The indices are usually sorted to make searching faster. The indices which
are sorted are known as ordered indices.
● Example: Suppose we have an employee table with thousands of record and
each of which is 10 bytes long. If their IDs start with 1, 2, 3....and so on and
we have to search student with ID-543.
● In the case of a database with no index, we have to search the disk block
from starting till it reaches 543. The DBMS will read the record after reading
543*10=5430 bytes.
● In the case of an index, we will search using indexes and the DBMS will read
the record after reading 542*2= 1084 bytes which are very less compared to
the previous case.

Excellence and Service

 CHRIST
Deemed to be University

Primary Index

● If the index is created on the basis of the primary key of the table, then it is
known as primary indexing. These primary keys are unique to each record
and contain 1:1 relation between the records.
● As primary keys are stored in sorted order, the performance of the searching
operation is quite efficient.
● The primary index can be classified into two types:
○ Dense index and
○ Sparse index.

Excellence and Service

 CHRIST
Deemed to be University

Dense index

● The dense index contains an index record for every search key value in the
data file. It makes searching faster.
● In this, the number of records in the index table is same as the number of
records in the main table.
● It needs more space to store index record itself. The index records have the
search key and a pointer to the actual record on the disk.

Excellence and Service

 CHRIST
Deemed to be University

Sparse index

● Here, the index record appears only for a few items in the data file. Each item
points to a block.
● sparse Index stores index records for only some search-key values. It needs
less space, less maintenance overhead for insertion, and deletions but It is
slower compared to the dense Index for locating records.

Excellence and Service

 CHRIST
Deemed to be University

Clustering Index

● A clustered index can be defined as an ordered data file.

Sometimes the index is created on non-primary key
columns which may not be unique for each record.
● In this case, to identify the record faster, we will group
two or more columns to get the unique value and create
index out of them. This method is called a clustering
index.
● The records which have similar characteristics are
grouped, and indexes are created for these group.

Excellence and Service

 CHRIST
Deemed to be University

Example: suppose a company

contains several employees in
each department. Suppose we
use a clustering index, where
all employees which belong to
the same Dept_ID are
considered within a single
cluster, and index pointers
point to the cluster as a whole.
Here Dept_ID is a non-unique
key.

Excellence and Service

 CHRIST
Deemed to be University

Secondary Index

● In the sparse indexing, as the size of the table grows, the size of mapping
also grows. These mappings are usually kept in the primary memory so that
address fetch should be faster. Then the secondary memory searches the
actual data based on the address got from mapping. If the mapping size
grows then fetching the address itself becomes slower. In this case, the
sparse index will not be efficient. To overcome this problem, secondary
indexing is introduced.
● In secondary indexing, to reduce the size of mapping, another level of
indexing is introduced. In this method, the huge range for the columns is
selected initially so that the mapping size of the first level becomes small.
Then each range is further divided into smaller ranges. The mapping of the
first level is stored in the primary memory, so that address fetch is faster. The
mapping of the second level and actual data are stored in the secondary
memory (hard disk).
Excellence and Service
 CHRIST
Deemed to be University

● If you want to find the

record of roll 111 in the
diagram, then it will search
the highest entry which is
smaller than or equal to 111
in the first level index. It will
get 100 at this level.
● Then in the second index
level, again it does max
(111) <= 111 and gets 110.
Now using the address 110,
it goes to the data block
and starts searching each
record till it gets 111.
● This is how a search is
performed in this method.
Inserting, updating or
deleting is also done in the
same manner.
Excellence and Service
 CHRIST
Deemed to be University

Multi-level Indexing

● Btree
● B+ tree

Excellence and Service

 CHRIST
Deemed to be University

Btree

● B Tree is a specialized m-way tree that can be widely used for disk access. A
B-Tree of order m can have at most m-1 keys and m children. One of the
main reason of using B tree is its capability to store large number of keys in a
single node and large key values by keeping the height of the tree relatively
small.
● A B tree of order m contains all the properties of an M way tree. In addition, it
contains the following properties.
1. Every node in a B-Tree contains at most m children.
2. Every node in a B-Tree except the root node and the leaf node contain at least m/2
children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.

Excellence and Service

 CHRIST
Deemed to be University

● It is not necessary that, all the nodes contain the same number of children
but, each node must have m/2 number of nodes.
● A B tree of order 4 is shown in the following image.

● While performing some operations on B Tree, any property of B Tree may

violate such as number of minimum children a node can have. To maintain
the properties of B Tree, the tree may split or join.

Excellence and Service

 CHRIST
Deemed to be University
Searching in a B Tree
● Searching in B Trees is similar to that in Binary search tree. For example, if we
search for an item 49 in the following B Tree. The process will something like
following :
● Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
● Since, 40<49<56, traverse right sub-tree of 40.
● 49>45, move to right. Compare 49.
● match found, return.
● Searching in a B tree depends upon the height of the tree. The search algorithm
takes O(log n) time to search any element in a B tree.

Excellence and Service

 CHRIST
Deemed to be University

Inserting a node in B Tree

● Insertions are done at the leaf node level. The following algorithm needs to be followed in order to insert an
item into B Tree.
● Traverse the B Tree in order to find the appropriate leaf node at which the node can be inserted.
● If the leaf node contain less than m-1 keys then insert the element in the increasing order.
● Else, if the leaf node contains m-1 keys, then follow the following steps.
○ Insert the new element in the increasing order of elements.
○ Split the node into the two nodes at the median.
○ Push the median element upto its parent node.
○ If the parent node also contain m-1 number of keys, then split it too by following the same steps.
● Example:
● Insert the node 8 into the B Tree of order 5 shown in the following image.
8 will be inserted to the
right of 5, therefore
insert 8.

Excellence and Service

 CHRIST
Deemed to be University

● The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys.

Therefore split the node from the median i.e. 8 and push it up to its parent
node shown as follows.

Excellence and Service

 CHRIST
Deemed to be University

Deletion Operation in B Tree

● Deletion
● Deletion is also performed at the leaf nodes. The node which is to be deleted can either be a leaf node or
an internal node. Following algorithm needs to be followed in order to delete a node from a B tree.
● Locate the leaf node.
● If there are more than m/2 keys in the leaf node then delete the desired key from the node.
● If the leaf node doesn't contain m/2 keys then complete the keys by taking the element from eight or left
sibling.
○ If the left sibling contains more than m/2 elements then push its largest element up to its parent and move the intervening element
down to the node where the key is deleted.
○ If the right sibling contains more than m/2 elements then push its smallest element up to the parent and move intervening element
down to the node where the key is deleted.
● If neither of the sibling contain more than m/2 elements then create a new leaf node by joining two leaf
nodes and the intervening element of the parent node.
● If parent is left with less than m/2 nodes then, apply the above process on the parent too.
● If the the node which is to be deleted is an internal node, then replace the node with its in-order successor
or predecessor. Since, successor or predecessor will always be on the leaf node hence, the process will be
similar as the node is being deleted from the leaf node.
● Example 1
● Delete the node 53 from the B Tree of order 5 shown in the following figure.

Excellence and Service

 CHRIST
Deemed to be University

53 is present in the right child of

element 49. Delete it.

● Now, 57 is the only element which is left in the node, the minimum number of elements that must be
present in a B tree of order 5, is 2. it is less than that, the elements in its left and right sub-tree are also not
sufficient therefore, merge it with the left sibling and intervening element of parent i.e. 49.

Excellence and Service

 CHRIST
Deemed to be University

● The final B tree is shown as follows.

Application of B tree
● B tree is used to index the data and provides fast access to the actual data
stored on the disks since, the access to value stored in a large database that
is stored on a disk is a very time consuming process.
● Searching an un-indexed and unsorted database containing n key values
needs O(n) running time in worst case. However, if we use B Tree to index
this database, it will be searched in O(log n) time in worst case.
Excellence and Service
 CHRIST
Deemed to be University
B+ tree

● The B+ tree is a balanced binary search tree. It follows a multi-level index format.
● In the B+ tree, leaf nodes denote actual data pointers. B+ tree ensures that all leaf
nodes remain at the same height.
● In the B+ tree, the leaf nodes are linked using a link list. Therefore, a B+ tree can
support random access as well as sequential access.
Structure of B+ Tree
○ In the B+ tree, every leaf node is at equal distance from the root node. The B+
tree is of the order n where n is fixed for every B+ tree.
○ It contains an internal node and leaf node.

Excellence and Service

 CHRIST
Deemed to be University

● Internal node
○ An internal node of the B+ tree can contain at least n/2 record pointers except
the root node.
○ At most, an internal node of the tree contains n pointers.
● Leaf node
○ The leaf node of the B+ tree can contain at least n/2 record pointers and n/2 key
values.
○ At most, a leaf node contains n record pointer and n key values.
○ Every leaf node of the B+ tree contains one block pointer P to point to next leaf
node.

Excellence and Service

 CHRIST
Deemed to be University

Searching a record in B+ Tree

● Suppose we have to search 55 in the below B+ tree structure. First, we will

fetch for the intermediary node which will direct to the leaf node that can
contain a record for 55.
● So, in the intermediary node, we will find a branch between 50 and 75 nodes.
Then at the end, we will be redirected to the third leaf node. Here DBMS will
perform a sequential search to find 55.

Excellence and Service

 CHRIST
Deemed to be University

B+ Tree Insertion

● Suppose we want to insert a record 60 in the below structure. It will go to the

3rd leaf node after 55. It is a balanced tree, and a leaf node of this tree is
already full, so we cannot insert 60 there.
● In this case, we have to split the leaf node, so that it can be inserted into tree
without affecting the fill factor, balance and order.

Excellence and Service

 CHRIST
Deemed to be University

● The 3rd leaf node has the values (50, 55, 60, 65, 70) and its current root node
is 50. We will split the leaf node of the tree in the middle so that its balance is
not altered. So we can group (50, 55) and (60, 65, 70) into 2 leaf nodes.
● If these two has to be leaf nodes, the intermediate node cannot branch from
50. It should have 60 added to it, and then we can have pointers to a new leaf
node.

● This is how we can insert an entry when there is overflow. In a normal

scenario, it is very easy to find the node where it fits and then place it in that
leaf node.
Excellence and Service
 CHRIST
Deemed to be University

B+ Tree Deletion

● Suppose we want to delete 60 from the above example. In this case, we have
to remove 60 from the intermediate node as well as from the 4th leaf node
too. If we remove it from the intermediate node, then the tree will not satisfy
the rule of the B+ tree. So we need to modify it to have a balanced tree.
● After deleting node 60 from above B+ tree and re-arranging the nodes, it will
show as follows:

Excellence and Service

 CHRIST
Deemed to be University
Difference Between Btree and B+tree
B tree B+ tree
In the B tree, all the keys and records are stored in both In the B+ tree, keys are the indexes stored in the internal nodes and
internal as well as leaf nodes. records are stored in the leaf nodes.
In B tree, keys cannot be repeatedly stored, which In the B+ tree, there can be redundancy in the occurrence of the keys. In
means that there is no duplication of keys or records. this case, the records are stored in the leaf nodes, whereas the keys are
stored in the internal nodes, so redundant keys can be present in the
internal nodes.
In the Btree, leaf nodes are not linked to each other. In B+ tree, the leaf nodes are linked to each other to provide the sequential
access.
In Btree, searching is not very efficient because the In B+ tree, searching is very efficient or quicker because all the records are
records are either stored in leaf or internal nodes. stored in the leaf nodes.
Deletion of internal nodes is very slow and a time- Deletion in B+ tree is very fast because all the records are stored in the leaf
consuming process as we need to consider the child of nodes so we do not have to consider the child of the node.
the deleted key also.
In Btree, sequential access is not possible. In the B+ tree, all the leaf nodes are connected to each other through a
pointer, so sequential access is possible.
In Btree, the more number of splitting operations are B+ tree has more width as compared to height.
performed due to which height increases compared to
width,
In Btree, each node has atleast two branches and each In B+ tree, internal nodes contain only pointers and leaf nodes contain
node contains some records, so we do not need to records. All the leaf nodes are at the same level, so we need to traverse till
traverse till the leaf nodes to get the data. the leaf nodes to get the data.
The root node contains atleast 2 to m children where m The root node contains atleast 2 to m children where m is the order of the
is the order of the tree. tree.

Excellence and Service

 CHRIST
Deemed to be University

Hashing

● In a huge database structure, it is very inefficient to search all the index

values and reach the desired data. Hashing technique is used to calculate the
direct location of a data record on the disk without using index structure.
● In this technique, data is stored at the data blocks whose address is
generated by using the hashing function. The memory location where these
records are stored is known as data bucket or data blocks.
● In this, a hash function can choose any of the column value to generate the
address. Most of the time, the hash function uses the primary key to generate
the address of the data block. A hash function is a simple mathematical
function to any complex mathematical function. We can even consider the
primary key itself as the address of the data block. That means each row
whose address will be the same as a primary key stored in the data block.

Excellence and Service

 CHRIST
Deemed to be University

Excellence and Service

 CHRIST
Deemed to be University

● The above diagram shows data block addresses same as primary key value.
This hash function can also be a simple mathematical function like
exponential, mod, cos, sin, etc. Suppose we have mod (5) hash function to
determine the address of the data block. In this case, it applies mod (5) hash
function on the primary keys and generates 3, 3, 1, 4 and 2 respectively, and
records are stored in those data block addresses.

Excellence and Service

 CHRIST
Deemed to be University

Types of Hashing

● Static hashing
● Dynamic hashing

Excellence and Service

 CHRIST
Deemed to be University
Static Hashing
● In static hashing, the resultant data bucket address will always be the same.
That means if we generate an address for EMP_ID =103 using the hash
function mod (5) then it will always result in same bucket address 3. Here,
there will be no change in the bucket address.
● Hence in this static hashing, the number of data buckets in memory remains
constant throughout. In this example, we will have five data buckets in the
memory used to store the data.

Excellence and Service

 CHRIST
Deemed to be University

Operations of Static Hashing

● Searching a record
○ When a record needs to be searched, then the same hash function retrieves the address of the
bucket where the data is stored.
● Insert a Record
○ When a new record is inserted into the table, then we will generate an address for a new
record based on the hash key and record is stored in that location.
● Delete a Record
○ To delete a record, we will first fetch the record which is supposed to be deleted. Then we will
delete the records for that address in memory.
● Update a Record
○ To update a record, we will first search it using a hash function, and then the data record is
updated.
○ If we want to insert some new record into the file but the address of a data bucket generated
by the hash function is not empty, or data already exists in that address. This situation in the
static hashing is known as bucket overflow. This is a critical situation in this method.
○ To overcome this situation, there are various methods. Some commonly used methods are as
follows:
■ Open Hashing
■ Close hashing

Excellence and Service

 CHRIST
Deemed to be University

Open Hashing

● When a hash function generates an address at which data is already stored,

then the next bucket will be allocated to it. This mechanism is called
as Linear Probing.
● For example: suppose R3 is a new address which needs to be inserted, the
hash function generates address as 112 for R3. But the generated address is
already full. So the system searches next available data bucket, 113 and
assigns R3 to it.

Excellence and Service

 CHRIST
Deemed to be University

Close Hashing
● When buckets are full, then a new data bucket is allocated for the same hash
result and is linked after the previous one. This mechanism is known
as Overflow chaining.
● For example: Suppose R3 is a new address which needs to be inserted into
the table, the hash function generates address as 110 for it. But this bucket is
full to store the new data. In this case, a new bucket is inserted at the end of
110 buckets and is linked to it.
●

Excellence and Service

 CHRIST
Deemed to be University

Dynamic Hashing
● The dynamic hashing method is used to overcome the problems of static
hashing like bucket overflow.
● In this method, data buckets grow or shrink as the records increases or
decreases. This method is also known as Extendable hashing method.
● This method makes hashing dynamic, i.e., it allows insertion or deletion
without resulting in poor performance.

How to search a key

● First, calculate the hash address of the key.
● Check how many bits are used in the directory, and these bits are called as i.
● Take the least significant i bits of the hash address. This gives an index of the
directory.
● Now using the index, go to the directory and find bucket address where the
record might be.

Excellence and Service

 CHRIST
Deemed to be University

How to insert a new record

● Firstly, you have to follow the same procedure for retrieval, ending up in some
bucket.
● If there is still space in that bucket, then place the record in it.
● If the bucket is full, then we will split the bucket and redistribute the records.
● For example: Consider the following grouping of keys into buckets, depending
on the prefix of their hash address:
The last two bits of 2
and 4 are 00. So it will
go into bucket B0. The
last two bits of 5 and 6
are 01, so it will go into
bucket B1. The last
two bits of 1 and 3 are
10, so it will go into
bucket B2. The last
two bits of 7 are 11, so
it will go into B3.

Excellence and Service

 CHRIST
Deemed to be University

Insert key 9 with hash address 10001 into the above

structure:
● Since key 9 has hash address 10001, it must go into the first bucket. But
bucket B1 is full, so it will get split.
● The splitting will separate 5, 9 from 6 since last three bits of 5, 9 are 001, so it
will go into bucket B1, and the last three bits of 6 are 101, so it will go into
bucket B5.
● Keys 2 and 4 are still in B0. The record in B0 pointed by the 000 and 100
entry because last two bits of both the entry are 00.
● Keys 1 and 3 are still in B2. The record in B2 pointed by the 010 and 110
entry because last two bits of both the entry are 10.
● Key 7 are still in B3. The record in B3 pointed by the 111 and 011 entry
because last two bits of both the entry are 11.

Excellence and Service

 CHRIST
Deemed to be University

Excellence and Service

 CHRIST
Deemed to be University

Advantages of dynamic hashing

● In this method, the performance does not decrease as the data grows in the
system. It simply increases the size of memory to accommodate the data.
● In this method, memory is well utilized as it grows and shrinks with the data.
There will not be any unused memory lying.
● This method is good for the dynamic database where data grows and shrinks
frequently.

Disadvantages of dynamic hashing

● In this method, if the data size increases then the bucket size is also
increased. These addresses of data will be maintained in the bucket address
table. This is because the data address will keep changing as buckets grow
and shrink. If there is a huge increase in data, maintaining the bucket address
table becomes tedious.
● In this case, the bucket overflow situation will also occur. But it might take
little time to reach this situation than static hashing.
Excellence and Service
 CHRIST
Deemed to be University

SQL Query Processor

1. Parsing and translation

2. Optimization
3. Evaluation

Excellence and Service

 CHRIST
Deemed to be University

[
1. The first step is to transform the query into a standard form.
2. A query is translated into SQL and into a relational algebraic expression. During this process, Parser
checks the syntax and verifies the relations and the attributes which are used in the query.
Example:
SELECT Ename FROM Employee
WHERE Salary > 5000;
Translated into Relational Algebra Expression
σ Salary > 5000 (π Ename (Employee))
OR
π Ename (σ Salary > 5000 (Employee))

3. The second step is Query Optimizer. In this, it transforms the query into equivalent expressions that are
more efficient to execute.

4. The third step is Query evaluation. It executes the above query execution plan and returns the result.

Excellence and Service

 CHRIST
Deemed to be University

Thank you

Excellence and Service