Storage Structures - Database Management System Video Lecture - Computer Science Engineering (CSE)

ah ha ha they just mean
at what might be termed as the logical
aspects of database design we looked at
different data models how data can be
represented and how the relationships
between them can be represented
we saw the ER schema which is meant
primarily for human comprehension and we
also saw the relational schema which we
claimed is meant for the physical schema
that is meant for machine comprehension
but when you say physical schema it is
still a kind of misnomer because the the
relational data model does not say
anything about how data is actually
stored on computers or storage devices
like disks or whatever wherever
databases are implemented so in this
session and the next few sessions we are
going to actually rip apart in a sense
look inside a DBMS or inside an
implementation of a DBMS and see how are
these data elements actually stored on
computers and what does it mean when we
say that we have stored a table how is a
table actually residing on on disks or
or any other kind of storage device so
that is what we are going to be
concerned with in the next few sessions
so let us begin the session on storage
structures in order to be understanding
the storage structures one of the first
things we need to understand is the what
might be termed as the memory hierarchy
when we talk about storage or storing
data the first question we need to ask
is where is data stored there are
different kinds of devices which which
are capable of storing data you might
you might have obviously come across a
hard disk serving data that are storing
stored in hard disks floppy disks cd-rom
and even the computer RAM that is the
random access memory in the computer the
cache memory within within the machine
and even the registers are within the
CPU all of them are meant for storing
data and all of these can be organized
this kind of
kinds of different cancers memory
devices can be organized in the form of
a hierarchy which is termed as a memory
hierarchy this slide shows such a memory
hierarchy but it divides this hierarchy
into two kinds of storage devices what
are called as primary storage and what
are called as secondary storage if I
were to draw a hierarchy primary
storages would storage devices would
would appear up in the hierarchy and
below them would be the secondary
storage devices what is the difference
between the primary and secondary
storage devices primary storage devices
some examples are shown in the slide
here like CPU registers cache memory Ram
DRAM SRAM and so on all of them are
extremely fast memory devices you can
address or retrieve data elements
extremely fast from from these devices
however all of these are volatile memory
devices that means once the power is
switched off they no longer can hold
data data that are stored in primary
storage devices cannot be persistent in
in nature on the other hand secondary
storage devices which of which some
examples are magnetic disks like your
hard disk on your PC
magnetic tape which is primarily used in
many locations for archiving data or
taking backups of data then there are CD
ROMs there are read-only CD ROMs there
are write-once CD ROMs there are even
some kind of readwrite CD ROMs that that
are being available today and there are
also what what is a more recent
phenomenon with what is called as the
flash memory flash memory is a kind of
is made of water called as a eproms that
is electrically or erasable programmable
read only memories which can store data
persistently even after the power is
switched off and they can perform or
they can perform data transfer in a rate
that is much faster than existing
storage devices like say magnetic disks
or tapes and so on so the common theme
in the in secondary storage devices is
that data can be stored in these devices
in a persistent fashion and usually
secondary storage devices are much
cheaper than primary storage devices and
they can store much more data than can
be stored in a primary storage device
however usually secondary storage
devices are much slower to access they
incur much more overheads in during
access than accessing a primary storage
device like say RAM or cache memory or
so now for the most part when
implementing a database management
system we shall be concerned mainly with
secondary storage devices we do not
concern ourselves with what are called
as main memory databases which which are
which are databases that are completely
held in main memory there there are not
many implementations of main memory
databases simply because it is much much
more expensive to to have large main
memories which which can implement
databases of a sizeable of a pretty
large size so secondary storage devices
have certain kinds of certain
characteristics which which are
important or which influence the kind of
storage structure that we are going to
use to to access and store and access
data in these devices we can either
categorize a secondary storage devices
either a random access device or a
sequential device something like the PC
hard disk or magnetic disks are random
access devices that is you can access
any given block of data in in a in a
magnetic disk they are called sectors so
you can you can access any particular
sector directly it is not purely random
access because it does perform some kind
of sequential searches however for for
most practical purposes a mounted
magnetic disk is a random access device
where you can you can address any block
directly and move to that block read or
write to that block directly on the
other hand something like a magnetic
tape is a sequential access device if
you have to access the
block and and the tape is rebound you
have to run through the first 99 blocks
before being able to access the
hundredth block
therefore it is it is important what
what kinds of how efficient can can data
access be when when we are using a
device which is either random axis or
sequential for example we cannot
implement a storage structure that that
has to perform a lot of passes on on the
data mainly because especially when we
are using a sequential device similarly
we can classify devices as either
read/write devices write-once devices or
read-only devices readwrite devices are
those where you can read and write data
any number of times hard disks floppy
disks magnetic tapes and so on are
examples on the other hand there are
right ones devices with where you can
write data once but you cannot erase it
once it is written it becomes a
read-only device so so such kinds of
devices cannot incorporate data
structures which need to be modified
during runtime for example similarly
there are read-only devices which where
data is stored during the manufacture of
the device itself and it can never be
altered and and so the new data cannot
be stored on such devices again so there
are devices especially in in embedded
systems which which store small
databases within read-only devices and
it is extremely important that such
storage is a is is performed correctly
the first time because there is no scope
for any kind of modifications once data
is written on to these devices then
there are devices that can be classified
as either character devices or block
devices character devices of those where
you have to read data character by
character which can be extremely
inefficient when we are dealing with
large amounts of data some kinds of tape
devices and so on our character
on the other hand there are block data
access devices where usually the the
unit of data transfer is a set of
characters called a block so every time
any read request is given a read request
reads an entire block of data into
memory and writes back an entire block
of data onto the device and usually the
block access is coupled with what are
called as reader heads that means it is
not just one block it is a set of blocks
that are read into memory at a given
point in time in order to increase data
transfer efficiency what are the
requirements for storing databases what
kinds of storage requirements to do two
databases pose firstly we note that
almost all databases require data to be
stored permanently or what is called as
persistently for longer periods of time
it should not be the case that once the
computer is switched off there all the
data in the database is lost it has to
be stored permanently or in a persistent
fashion usually databases are far too
big to fit in main memory it is not
realistic to to be able to search a
database by loading the entire database
into memory and then use such techniques
on that are mainly useful for main
memory we have to store the database on
disk and involve strategies that can
search data on on to the disk and use
memory for for this purpose over the
years the the cost of storage has
dropped drastically in fact there are
many claims that the progress in storage
has bitten what is called as Moore's Law
that is the amount of storage that can
be packed into a given cost for a given
cost on a given square area of physical
dimensions today we can we can have
gigabytes of data stores in a very small
device that one can store within your in
pockets or
in a very small area we have gigabytes
of data stores that that are embedded
within watches for example and within
pens and so on so the amount of the data
store that that the storage available
per person has increased dramatically
over the years and one of the byproduct
of this is the changing definition of
what might be termed as very large
databases in fact the term very large
databases when it was coined was meant
to refer to databases which are hundreds
of megabytes large slowly very large
databases came to mean several gigabytes
of data and now we have databases that
are several hundreds of gigabytes or
terabytes which are 10 to the power of
12 bytes and then even petabytes of data
petabytes are 10 power 15 bytes of data
where especially databases that work on
web related data like like Google or
Alta boosters are search engines which
which collect data from all over the web
actually work on petabytes of data so so
the definition of very large databases
has been changing continuously to
include more and more data storage
requirements therefore what is being
what has become imperative today is to
design extremely agile data structures
that can that can store and manage data
between main memory and second storage
devices in a in an efficient fashion
when we store data onto a secondary
memory we usually distinguish between
two kinds of data storage the one is
what is called as a primary data storage
the primary data storage talks about how
we store the data itself how data itself
is organized on on to disks or any
storage device and how are the axis
secondary file structures are those are
also called as auxiliary or augmenting
files
structures are those sets of files that
are used to speed up access to these
data elements and this is especially
important secondary file organizations
become especially important when the
size of the database starts growing by
leaps and bounds when we have terabytes
or petabytes of data it is the role of
auxiliary files or secondary files that
that provide pointers that that help us
in locating the required data elements
becomes more and more important usually
when we talk about the data storage on
on secondary devices we are we are
talking about what what is termed as
file organizations data is stored in
logical structures called files on on
disk the way files are organized on disk
is called the file organizations usually
files are stored as a sequence of
Records and a record is a is analogous
to the notion of a tuple in a relation
in relational algebra or a row in a in
SQL parlance so a file is stored as a
sequence of these physical or logical
records and understood in terms of water
called as physical blocks as we as we
saw before in the previous slide the
block is the unit of data transfer
between main memory and the storage
device so so there are two different
things here within a file one is the
logical ordering of data which is in the
form of Records and then the physical
storage of data which is in the term
terms of blocks there could be one is to
one correspondence between records and
blocks which is very rare which means to
say that each block is one record or
there could be many records per block or
many blocks per record depending on how
we define our record structure the the
term file organization refers to the way
in which records are stored in terms of
blocks
and in the web blocks are placed on the
storage medium under interlinked so that
they can be accessed from one there are
three different kinds of file
organizations that we are going to see
in this session today the first one is
what is called as the unsorted or the
pile file organization and the second
kind of organization is what is called
as a sorted file organization and lastly
we are going to look at hashing file
organization let us briefly look at the
notion of record and blocks which is
important for us to understand these
different kinds of file organizations a
record like we mentioned earlier
represents a tuple in any relation it is
a logical unit of data which of
interrelated data which is of interest
to the user or the database management
system a file is defined as a sequence
of records and records could either be
fixed length or variable length remember
in SQL for example you can use variable
length strings and variable length
integers and so on so so the length of a
given record could also be variable or
fixing and records comprised of a
sequence of different fields and fields
is the same as a field is the same as a
column by in SQL parlance are are an
attribute in relational parlance blocks
so blocks like we mentioned earlier is
the physical unit of data transfer data
storage in storage devices they
correspond to for example sectors in in
hard disk or page in virtual memory
systems and so on this store usually a
block stores records from a single file
but it need not necessarily be such a
case it depends on depends on the file
system structure blocks are usually of
fixed length blocks cannot be of varying
length unlike records and the length of
a block is dependent upon physical
characteristics of the storage device
and also of the operating system and the
rammons
one so many times the database
management system itself does not have
much control or the size of a block a
storage device is termed to be either
defragmented or fragmented depending on
whether contiguous sets of blocks on the
storage device belong to the same file
or are two different files we now define
a term called the blocking factor which
is important to to determine how records
are packed within blocks the blocking
factor is the number of records that are
stored in a block on a given storage
device it is constant across blocks the
this blocking factor is constant across
blocks if record length is fixed on the
other hand if record length is variable
then the blocking factor is also
variable because the number of Records
per block may vary from block to block
blocking factor is simply defined as the
number of blocks divided by the are the
size of block divided by the size of the
total number of Records so bfr as shown
in the slide is is B divided by R where
B is block size and R is record size and
this is a floor function that is a which
takes a lower integer value of this
division since the record size may not
exactly divide block size there will be
some amount of wastage which is given by
this formula that is a each block in
each block there is a wastage of this
much amount of bytes that is a blocking
factor times the record size number of
bytes so how is this wastage wastage
managed there are two kinds of
approaches to managing this wasted block
area when records are stored within
blocks the first is to do nothing that
is do not use a let wasted spaces be
such kinds of techniques are used in
what are called as unspent records that
is a record may not span multiple blocks
this
a slide shows such an example the slide
shows one block which spans from here to
here compressing of three different
records and there is no space for a
fourth record however there is some
extra space that is left in the block
which is left unused on the other hand
there are what are called as spanned
records a spanned record is something
that can span across different blocks
this slide shows such an example this
block contains three records and there
is not enough space for the fourth
record however part of the fourth record
is placed in the remaining space leaving
a small amount of space for a pointer to
point to the next block in the air in
the logical sequence of records and very
well the next block begins the remaining
part of the fourth record is stored and
then the next records are stored here so
such kinds of record organizations are
attempt to be spanning organizations
where a record can span across multiple
blocks I am sure you would have noticed
that if record size is bigger than the
block size we have to necessarily use
the spanning organization for storing
records because we cannot store records
into blocks otherwise so this is what
this slide says that is when when record
size is greater than the block size that
is R is greater than B then a usage of
spanned records is compulsory when you
have variable record sizes or when we
use spanned record allocation we can we
can term what is called as the average
number of blocks that are required per
or we can compute what is called as the
average number of blocks required for
storing a collection of Records so this
can be in order to compute this we first
simply compute the blocking factors that
is the block size divided by the average
size of each record then the following
formula where where R is the number of
Records divided by the blocking factor
give the number of blocks that is
required for storing a particular
database that is a particular set of
Records let us now start with the
different kinds of file organization
techniques the first kind of file
organization technique that we are going
to see today is what is called as the
unordered file organization this is also
termed as a pile file where the term
meaning that records are just stored as
a pile inside the file this slide shows
such an example that is records are
coming in into the system and they are
just being appended to the file record
one record to record three record four
without recourse to what data that are
contained in these records and how they
are going to be searched and of course
this data these records eventually go
into different blocks and they are
managed in some fashion by the operating
system in underneath in the machine a
pile file is the simplest form of file
organization we do not have to do
anything for for organizing this file
and insertion of Records is the simplest
that is records are inserted in the
order of their arrival and on the other
hand if you have to search this file we
usually need some kinds of auxiliary
files or we require some kind of help in
order to efficiently search these files
for a given data element therefore
insertion is very easy
however searching is extremely expensive
because we will have to do a linear
search we have to just search through
the entire file in order to find the
data element that we require what about
deletion in pile files deletion possess
yet another tricky problem in in pile
files and which can create certain kinds
of fragmentation problems have a look at
the slide here the slide shows a pile
file containing three records and some
part of the block is is empty and there
are other blocks as well in the in the
file now suppose that record too has to
be deleted now once we delete record too
and empty the space we cannot reclaim
back the space because the insertion
algorithm for for a pile file is not
cognizant of this of this extra space
that it can use in the insertion
algorithm simply inserts records into at
the end of the file it just appends
records to the file therefore such a
kind of deletion strategy is inefficient
in terms of space use usage when we are
using variable length records in a pile
file we encounter another unique problem
and this is a record modification
whenever some data is modified in a
record as long as the record is a fixed
length it does not matter we can make
the modification in place and write it
back into the file however if we allow
for records to have variable size and
the modification results in in in the
size of the record to grow there may not
be enough space to write back the record
this slide shows such a example there
are three records in this file or rather
four records in the file record one
record to record three in record four
and record two is modified now the
modification is such that the size of
record two increases now we cannot write
back this record at the same place where
it was earlier therefore we'll have to
mark this mark the earlier record as
deleted or unused or something like that
and write back record too at the end of
the file this is shown in the figure
here and of course we need to update any
kind of auxiliary data structures that
that point to record too so that it
points to the new location in the file
the second kind of file organization
that we are going to consider are what
are called as sorted files sorted file
said those are those files which are
physically sorted on on the disk based
on some field called the ordering field
so the file is actually they are rather
physically sorted on the disk so when
you read the
file on disk in a particular order it it
provides or it returns back records
which are sorted based on the ordering
field ordering field should be a key
field or should or it is now it is
recommended that the ordering key
ordering field should be a key field
that is it should be unique for each
record and should belong to an ordinal
domain what is an ordinal domain an
ordinal domain is something where you
can establish a total order among the
among elements of the domain for example
the set of all integers is an ordinal
domain so the set of all names for
example is not an ordinal domain we
cannot place a 1 name with respect to
the other unless of course we impose
some kind of an ordering likes a lexical
ordering we say we order the names as
per the lexical rule that is a comes
before B B comes before C and so on in
sorted files insertion and deletion are
both expensive because we have to ensure
that the file remains sorted at all
times especially when a new record is
inserted with with a ordering field
which has to go somewhere in the middle
of the file rather than at the end of
the file and the updation of a record
may actually involve physical migration
of the record especially if the ordering
field is modified
however searching in a sorted file is is
made simpler because of the because we
can use what is termed as binary search
what is binary search we shall not go
into too much details of binary search
let me just give a small algorithm of
what a binary search looks like
essentially the the binary search
technique is a technique where we divide
the search space by half that is into
half in each iteration of the search
that is we reduce the search space into
half of the previous search space in
each iteration so this slide shows a
simple algorithm for by
researches we see in the first step here
that we start with two bounds left and
our lower and upper bound okay
the lower bound is at one that is the
first element or the first record and
the upper bound is said to be that is
where B is the number of blocks in the
file or the last block in the file and
in each iteration we are going to
compute the midpoint of these bounds
that is l plus u divided by two is the
midpoint now suppose we have to search
for a given key value K we say we read
the records from from block I that is
the midpoint and then see if and compare
that with the required key attribute now
there could be three different options
that is one is the key attribute is
equal to the key that that is read from
the block in which case we have found
the record therefore written we return a
success on the other hand a key
attribute could be less than the
midpoint in which case we have to search
the lower half of our search space that
is we have to search between 1 and I
minus 1 that is L and I minus 1 on the
other hand if key attribute is greater
than the midpoint we have to search in
the upper half of the database that is
we have to search between I plus 1 and
you so this this series of steps is
performed until until and unless R as
long as the U is greater than or equal
to L that is the upper bound is greater
than or equal to lower bound whenever
they cross that is whenever we whenever
the upper and lower bounds cross without
having found a given record we we are
able to conclude that the record does
not exist in the file and then we we say
it is not formed so binary search we are
not going to go into go into detailed
analysis of binary search here however
one can verify that a binary search
technique requires an order of or what
is termed as login where n is the number
of blocks in the in the
file a binary search requires an order
of login number of disk accesses whereas
a linear search which actually searches
through the file requires an order of n
number of block accesses for first
searching that is on an average n by 2
number of block X's have to be done for
a linear search whereas only log in to
base 2 number of axes need to be
performed for a binary search let us now
look at one more technique by which
sorted files can be made more efficient
in terms of insertion and updation note
that whenever a sorted file has whenever
a new record has to be inserted into a
sorted file it is it is always a problem
because the file has to be always sorted
physically on the disk it is not a
logical sorting that is being performed
here therefore whenever a new record is
being inserted as shown in the slide
here let us say record with key 1 is is
already in the in the file next key
value of 3 is already in the file and
key value with 7 is already in the file
and now we we receive a record whose key
value is 4 now what do we do with this
record in fact this record has to appear
between record 3 and record 7 in the
file physically on the file that means
that we have to physically move record 7
below and then insert record 4 here so
that the file remains sorted this is an
extremely expensive operation especially
if a lot of insertion operations are
taking place in order to mitigate this
problem
another technique what is called as the
overflow file is used an overflow file
is a is a secondary file or another file
where records are stored in an unsorted
fashion whenever a new record is being
added to the to the database it is just
added to the record or the overflow file
in the form of a pile file
it's just appended to the overflow file
and periodically that is in a less
frequent fashion let us say once in a
month or once in a week or on a weekends
or something like that the overflow file
is merged into the master file or the
actual sorted file that is the the
overflow file is first sorted and there
are a number of merge algorithms that
can take two sorted files and merge them
together in an efficient fashion and
using this the overflow file is merged
back into the master file when such a
technique is is used for sorted files
searching also becomes a little bit
different from a pure binary search that
is whenever a key has to be searched we
can perform a binary search on the
master file and in case the key is not
found in the master file we have to
perform a linear search in the overflow
file so there are two kinds of searching
that that has to be done when overflow
files are used in sorted file
organizations so to summary sorted files
we see that sorted files are more
efficient than pile files especially for
key based searches however they're
suitable mainly for random access
devices note that if you have to perform
a binary search and binary search over a
tape device we may have to keep moving
back and forth in the in the tape device
quite often which makes it more which
makes it terribly inefficient therefore
binary searches are more suitable for
random access devices rather than
sequential devices
it is a better choice where a database
is mostly read only because insertion is
always a problem insertion and updation
is the problem you have to use overflow
files or physically move records and
merge and so on and mostly queries are
keyword key based retrievals the third
kind of file organization that we are
going to see today the third and the
last kind of file organization that we
are seeing today is what is called as
hashing file organization what is meant
by hashing hashing is a means of
providing very fast access
to records on certain search conditions
and what are these search conditions
these search conditions are usually the
Equality condition based on a key field
that is whenever I want a such a record
having a particular key attribute it is
not note that it is not something like
whose keys are less than a particular
key attribute or greater than a
particular key attribute and so on this
is useful only when we are searching for
records whose key attributes are equal
to the attributes attribute that is
given in the query hashing techniques
uses a what are called as hashing
functions are which are also termed as
randomizing functions that map
particular keys into buckets for hosting
records and just like sorted file
techniques even hashing techniques are
primarily suited for random access
devices before we go into how hashing is
performed on disk let us have a look at
what is called as internal hashing
internal hashing is is hashing that is
performed entirely in main memory and in
most database management systems hashing
is used extensively in main memory in
order to quickly access a given data
element among a set of data elements
that have been loaded on to memory so
usually such kinds of hashing techniques
uses an internal data structure that has
something like static array of M
different buckets and they are indexed
from 0 to M minus 1 and there are
several candidates for for such a
hashing function a simple candidate is
is to just compute the mod or the
remainder of the key with M that is the
M is where m is the number of buckets in
the for the hashing function there are
also other hashing algorithms called
folding the key where a given key
attribute is twisted and folded in
different ways in order to come out with
a number that that is uniformly randomly
distributed across the set of all
buckets that form the static array of
hash buckets there are also other
techniques like sampling the key and so
on which
we are not going to be seeing here
external hashing is is the hashing
technique that is used for managing data
on disks rather than in memory external
hashing comprises of blocks on the disks
which act as buckets and in turn are
augmented by one or more blocks that
hold the the hashing array itself or the
set of buckets that form the hashing
array itself so the figure here shows a
typical hashing process given a
particular record with the key attribute
came it is first put through a hashing
function it which is called hash of K
here and this hashing function Maps it
onto a particular index entry in in an
array of buckets each index entry here
in turn has an address of one or more
blocks which form this bucket usually
one block can be allocated to one bucket
or it could also be more than one blocks
that are allocated to one bucket this
once the block is identified this record
is just appended to this block so
whenever a search has to be made on this
key we have to make a sequential search
within the block however we can reduce
our search space drastically especially
when there are large number of records
but on to a single block or a set of
blocks that form a given hash bucket so
to summarize external hashing again
external hashing uses two levels of
indirection that is hashing into buckets
and searching within buckets a bucket is
usually one disk block or a set of
contiguous blocks which is also
important here that is there is no point
having non contiguous blocks as part of
hashing because we again need to store
some information on how to access these
blocks from from one another a bucket
can hold more than one record obviously
and also this depends on the record size
and we have to perform a sequential
search within a bucket
hashing has to has to contend with with
the contentious issue of what is called
as overflows what happens if we choose a
hashing function that tries to hash
every key onto a very small number of
buckets it especially this can
especially happen when the data set
itself could be could be skewed even if
the hashing function that we have chosen
is a reasonable one that is a given a
set of keys that are uniformly
distributed over a given range this
randomizing function uniformly
distributed or the set of all buckets
however if our data set itself is skewed
we have a large number of key values
near a particular value rather than all
across the range then the hashing
function would also be a correspondingly
skewed in such cases what happens is
that buckets could get overflowed that
is they could the number of records
stored in a bucket could could go beyond
the capacity of the bucket itself in
such cases there are several techniques
that are used for overflow management
there are three different techniques
that are that are primarily used the
first one is what is called as open
addressing open addressing simply says
that if this bucket is full just use the
next available bucket which has which
has some space in it so so once a
hashing function hash ascent of a
particular bucket and then we find that
it is full we start a sequential scan or
a linear scan of the bucket space for
the next available bucket in which we
can store the record the second kind of
technique that is used for managing
workflows is what is called as chaining
chaining is the technique of maintaining
a linked list of different buckets so
that when a particular bucket is full it
maintains a pointer to another disk
block or another set of disk blocks
acting as another bucket which can hold
some more data in and so on and when
that becomes full there is another chain
and so on however because a hashing has
to perform
sequential searches within buckets if we
encounter or if I end up with a long
chain of buckets it becomes terribly
inefficient in terms of searching then
the third kind of kind of technique is
what is called as rehashing where we try
to use another hashing function if the
first hashing function does not work
that is a maps to an overflow bucket we
use hashing function to and then see if
it works and then hashing function three
or whatever end and then combine it with
something like something like open
addressing or chaining in order to
manage overflows so this slide here
shows the shows the concept of chaining
where there are main buckets here which
in turn have have pointers to overflow
buckets and this pointers point to exact
records in these overflow buckets and
each record here has a next record
pointer which points the next overflow
record that are that are managed by this
or few buckets until now we have been
looking at the kinds of hashing where
the bucket space or the number of
buckets is fixed such kinds of hashing
techniques are what are called as static
hashing techniques and we have already
seen what is the limitation of a static
hashing technique a given hashing
technique might work generally that is a
given hashing function might be good
enough so that if the sets of keys are
uniformly distributed the hashing is
also more or less uniformly distributed
however when the set of keys are skewed
when the data itself is skewed using a
static hashing might be terribly
inefficient because some amounts of
buckets could be overflowing while a
large number of other buckets could be
more or less empty in order to obviate
this need we use what is called as
dynamic hashing dynamic hashing is a is
a process where the number of buckets
can change dynamically can grow or
shrink with time as in when keys are
being added or deleted from the database
the overall strategy
dynamic hashing is is quite simple and
it is shown in the following three steps
the first is we just start with a single
bucket to begin with and and we hash
everything on to this bucket once the
bucket is full we split the bucket into
two separate buckets and then continue
with the hashing process this is and
then we redistribute the records or the
data that is stored within a bucket such
that they are more or less uniformly
distributed across the two different
buckets this process continues the
process of splitting continuous whenever
there is an overflow and then there is
the process of merging that happens
whenever there is an underflow that that
happens that is when a bucket becomes
empty we now look at a simple dynamic
hashing technique where we can which
shows how buckets are can be split and
merge the slide shows one such technique
here we see that we have a small diagram
here which shows two different kinds of
nodes or data structures this kind of
data structure the circle here is what
is called as an internal bucket and the
square or the rectangle here is what is
called as a leaf bucket or an external
bucket the leaf buckets are those which
actually store the data
initially all data is stored in a given
in a single bucket that is this is the
bucket for all records and assume that
now we are our keys are made of binary
strings and then we are storing all of
our data with these keys in these
records now suppose there is an overflow
that happens here in this bucket now
what happens when there is an overflow
this slide shows shows such a technique
that is when when there is an overflow
the bucket is split into two different
buckets and you can notice the labels
here for the edges joining these buckets
the first bucket is the set of all
records whose keys start with zero and
the second bucket is the set of all
records whose key start with one
assuming that our our keys are made of
binary strings now suppose there is an
again again an overflow in this
in this bucket and there is no
overflowing in the upper bucket here
what happens to the hash table then the
hash table then changes to this
following data structure where the
overflow bucket is split and a new
internal node is created and two
different buckets are are then created
so this bucket now is the set of all
holds the set of all records whose key
start with 1 0 whereas this bucket holds
the set of all records whose key start
with 1 1 so we can trace that starting
from the start start node here so 1 0
takes us to this bucket and 1 1 takes us
to this bucket what happens now if one
of this bucket of encounters an
underflow that is it becomes empty why
when when when records are deleted from
from the database we just have to merge
this bucket with with its partner so to
say that is a scene the diagram here
that this is the bucket whose edge is
labeled as 1 you have to just merge it
with its partner whose edges labeled 0
so this takes us back to the previous
configuration where we had only two
buckets in the hash table there is
another kind of dynamic hashing what is
called as extensible hashing which also
uses a similar kind of hashing technique
in order to grow and shrink buckets
extensible hashing uses of what is
termed as a global directory of 2 power
n number of bucket addresses where n is
called the global depth of the directory
and then each bucket is uniquely
identified by some set of higher order
bits D number of bits which is less than
or equal to n which can uniquely
identify each bucket and of course
buckets are split and merged whenever
there the overflow underflow and
correspondingly n is changed that is the
global depth is either increased or
decreased in a corresponding fashion
this slide shows such an example here we
have a global depth of 3 that is n equal
to 3 and there are several different
bucket pointers that shows 0 0 0 0 0 1
and so and so on
there are several different different
buckets each with differing capacity
we're here this bucket says that D equal
to 2 that means this bucket can be
uniquely identified with just the top
two bits that is all a key starting with
0 0 can go into this bucket here for
example D equal to 1 that is all key
starting with 1 go into this bucket but
here these two buckets have a large
number of data elements that is where D
equal to 3 that is this this bucket
contains all key is starting with 0 1 0
and this one contains all key starting
with 0 1 1 now suppose what happens is
the last bucket overflows that is where
D equal to 1 this bucket is a is then
split so that D becomes 2 and then
instead of a instead of just 1 bit we
have to use 2 bits in order to uniquely
identify this bucket
therefore the top bucket here the upper
bucket here is the set of all keys which
start with 1 0 and the lower bucket here
is the set of all keys that start with 1
1 so that brings us to the to the end of
this session where we have looked at
several kinds of file organizations and
for physically managing records on on
storage devices let us quickly summarize
what we have learnt in this in this
session we first looked at different
kinds of storage medium and what are
their characteristics we can classify
storage media in two different kinds
volatile non volatile primary secondary
and so on in fact they can be placed in
a hierarchy and then there are different
characteristics like random axis
sequential axis or read-only versus
readwrite or right ones and so on and
then there could be either character
devices or block devices and so on each
of them each of these characteristics
impact the kind of data structure that
we can use for storing records we then
look at the concepts of records blocks
and files which are the terminology we
use for dealing with data that are
physically stored on on to disks records
that the logical unit of data that are
stored while blocks of the
physical unit of data that that is a
that is used for data transfer and file
is the set of records or a sequential
records image are typically a relation
is stored we also saw the notion of
spanning and unspinning of records in
terms of how they affect the the
blocking factor are the number of blocks
that are required to store a particular
file of Records we then saw three
different fire kinds of file
organizations the first one was the pile
file organization which is the simplest
where we just append records into a file
however which poses problems with
insertion or rather with deletion and
updation and also with search we then
also saw sorted files which are files
that are physically sorted on disks
based on some ordering attribute sorted
files are much more efficient for search
because we can use binary search on
sorted files however there they pose
very tricky problems in terms of
insertion and updation of Records and
there especially they become especially
tricky when records can can be a very
englands and updations can change the
key value of on which it is sorted we
also saw the last kind of file
organization called hash files where a
hashing function is used in order to
identify the block number of the bucket
in which particular record is stored we
also saw how or what are the challenges
that that are faced by hash functions
especially when we use static hashing
techniques because static hashing
techniques cannot cannot work
efficiently when the data set is skewed
in which case we have to use dynamic
hashing where the number of buckets in
the hash table can dynamically grow or
shrink as and when data is inserted or
deleted so that brings us to the end of
this session
you