Transcript unit-v storage devic..

Disk Storage Devices


Disks are divided into concentric circular tracks on each
disk surface.
A track is divided into blocks.





The block size B is fixed for each system.
Typical block sizes range from B=512 bytes to B=8192 bytes.
Whole blocks are transferred between disk and main memory
for processing.
A physical disk block address consists of a surface
number, a track number (within surface), and a block
number (within track).
Reading or writing a disk block is time consuming
because of the seek time s and rotational delay (latency)
rd.
Update 2008
file-1
Database Speed Bottleneck




The data in the database is stored in files on the disk.
Therefore, the organization of files, and indexes to
access these files determine the performance of the
database system.
That is, performance of queries and transactions.
How crucial is the problem?



But,



Disk capacity has improved 1,000X in the last 15 year.
The size of data also has increased in the same rate.
platters only spin 4X faster.
the transfer rate has improved only 40X in the same period.
Thus:


disk accesses are more precious.
they are expected to be more precious in future.
Update 2008
file-2
O/S and hardware solutions

Buffering




Keep cache of recently accessed pages in main
memory
Arrange disks arrays: several disks that give
abstraction of a single, large disk.
Partition data into striping units and distribute
them over several disks.
But: more disks --> more failures!
Update 2008
file-3
Files of Records





File: is a sequence of records (tuples), where each record
is a collection of data values (or data items).
A file descriptor (or file header) includes information that
describes the file, such as the field names and their data
types, and the addresses of the file blocks on disk.
Records: are stored on disk blocks.
Length of records in a file
 fixed-length
 variable-length
Records can be
 unspanned (no record can span two blocks)
 spanned (a record can be stored in more than one
block)
Update 2008
file-4
Unordered Files
Also called a heap or a pile file.
 New records are inserted at the end of the file.
• To search for a record, a linear search through the
file records is necessary. This requires reading and
searching half the file blocks on the average, and is
hence quite expensive.
 Record insertion is quite efficient (by just appending).
 Reading the records in order of a particular field
requires sorting the file records.

Update 2008
file-5
Ordered Files



Also called a sequential file.
File records are kept sorted by the values of an
ordering field.
Insertion is expensive: records must be inserted in the
correct order.


A binary search can be used to search for a record on
its ordering field value.


separate unordered overflow (or transaction) file for new
records to improve insertion efficiency; this is periodically
merged with the main ordered file.
requires log2 of the file blocks on the average.
Reading the records in order of the ordering field is
quite efficient.
Update 2008
file-6
Static External Hashing

The file blocks are divided into



bucket0, bucket1,... bucketM-l.
One of the file fields (e.g., key) is
designated to be the hash key of the
file.
The record with hash key value K is
stored in bucketi, where:


M equal-sized buckets, numbered
i=h(K), and h is the hashing function.
Collisions occur when a new record
hashes to a bucket that is already full.


An overflow file is kept for storing such
records. Overflow records that hash to
each bucket can be linked together
To reduce overflow records, a hash file
is typically kept 70-80% full
Update 2008
file-7
Main and overflow buckets
Update 2008
file-8
Static External Hashing


The hash function h should distribute the
records uniformly among the buckets;
otherwise, search time will be increased
because many overflow records will exist.
Main disadvantages of static external hashing


Fixed number of buckets M is a problem if the
number of records in the file grows or shrinks.
Ordered access on the hash key is quite inefficient
(requires sorting the records).
Update 2008
file-9
Dynamic and Extendible Hashing
Techniques



Hashing techniques are adapted to allow the dynamic
growth and shrinking of the number of file records.
These techniques include the following: dynamic
hashing, extendible hashing, and linear hashing.
Both dynamic and extendible hashing use the binary
representation of the hash value h(K) in order to
access a directory.


In dynamic hashing the directory is a binary tree.
In extendible hashing the directory is an array of size 2d
where d is called the global depth.
Update 2008
file-10
Dynamic Hashing
Update 2008
file-11
Extensible Hashing
Update 2008
file-12
Dynamic and Extendible Hashing
Techniques



The directories can be stored on disk, and
they expand or shrink dynamically. Directory
entries point to the disk blocks that contain
the stored records.
An insertion in a disk block that is full causes
the block to split into two blocks and the
records are redistributed among the two
blocks. The directory is updated appropriately.
Dynamic and extendible hashing do not
require an overflow area.
Update 2008
file-13
Linear Hashing






Linear hashing does require an overflow area but
does not use a directory. Blocks are split in linear
order as the file expands.
The principle of linear hashing is incremental
reorganization.
The file space grows by appending blocks linearly to
the end of the hash space.
For collisions, which still occur, overflow blocks are
used.
Let M (power of 2) to indicate initial basic allocation;
the current allocation, M1 begins with M buckets.
The procedure operates unchanged until the file
reaches a size of 2M buckets. At that point the
records are adjusted to 2M buckets.
Update 2008
file-14
Linear Hashing - Lookup


The initial hash function is h0(K) = K mod M
When a collision leads to an overflow record in any file bucket







the bucket n = M1 - M is split into two buckets,
original bucket M1 - M, and the new bucket M1 + 1.
the value of M1 is now set to M1 + 1 (or n is incremented).
All the record in the original block are assigned to two blocks M1 - M,
and M1 + 1 by using the hash function h1(K) = K mod (2M).
The key property of two hash functions is that any records hashed
to bucket i based on h0 will be hashed to bucket i or bucket i + M
using hash function h1
To retrieve a record with key K first apply hash function h0(K);
if h0(K) < n; apply hash function h1(K) because bucket is split.
When n = M (or M1 = 2M)



all the blocks are split;
h1(K) applies to all records
reset M = M1 = 2M and n = 0.
Update 2008
file-15
Linear Hashing – Splitting and combining





Further, overflowing will cause use of hash function
h2(K) = K mod 4M to be used to split the buckets
In general, a sequence of hash functions
hj(K) = K mod 2jM is used, where j = 0, 1, 2...
The new hash function hj+1(K) is used when all the
buckets 0, 1, 2,..., 2jM -1 have been split.
Buckets that have been split can be combined if the
load of the file falls below some threshold.
The file load factor l = r/(bfr*N)




r is number of current records,
bfr is maximum number of records per bucket
N is the number of current file buckets (M1).
Blocks are combined linearly and M is decremented.
Update 2008
file-16
How Index are used?



Primary index : index on primary key. <e.g> s#
Secondary index: index on other field. <e.g> city
A given table may have any number of indexes.
<1> Sequential access :
City-Index
S (indexed file)
Athens
S1 ... ... London
London
S2 ... ... Paris
London
S3 ... ... Paris
Paris
S4 ... ... London
Paris
S5 ... ... Athens
accessed in the sequence defined by
values of the indexed field.
<e.g> Range query : "Find the suppliers whose
city begins with a letter in the range L-R."
<2> Direct Access :
<e.g> "Find suppliers in London."
<e.g> list query:"Find suppliers whose city
is in London, Paris, and N.Y."
<3> Existence test :
<e.g> "Is there any supplier in London ?"
Note: It can be done from the index alone.
Update 2008
file-17
Indexes as Access Paths



A single-level index is an auxiliary file that makes it
more efficient to, search for a record in the data file.
The index is usually specified on one field of the file
(although it could be specified on several fields).
One form of an index is a file of entries





<field value, pointer to record>,
which is ordered by field value.
The index is called an access path on the field.
The index file usually occupies considerably less disk
blocks than the data file because its entries are much
smaller.
A binary search on the index yields a pointer to the
file record.
Update 2008
file-18
Indexes as Access Paths
Example data file:

EMPLOYEE(NAME, SSN, ADDRESS,
JOB, SAL, ...)

Suppose that:






blocking factor records/block
Bfr=B/R = 512 /150= 3
number of file blocks
b=(r/Bfr)= (30000/3)= 10000
For an index on the SSN field




Then, we get:


record size R=150 bytes
block size B=512 bytes
r=30000 records


Then: index entry size
R1=(VSSN+ PR)=(9+7)= 16 bytes
Index blocking factor entries/block
Bfr1= B div R1= 512 div 16= 32
Number of dense index blocks
b1=(r/Bfr1)=(30000/32)=938
Number of non-dense index blocks
b2 = (b/ Bfr1)=(10000/32)= 313
Binary search needs block accesses



assume the field size VSSN=9 bytes
assume the record pointer size
PR=7 bytes.

log2b1= log2938=10
log2b2=log2313=9
This is compared to an average linear
search cost block accesses of:
(b/2)= 30000/2 = 15000
If the file records are ordered, the
binary search cost would be:

Update 2008
log2b = log230000= 15 block accesses
file-19
Single-Level Indexes – Primary Index





Defined on an ordered data file
The data file is ordered on a
INDEX FILE
BLOCK
BLOCK
key field
ANCHOR
POINTER
PRIMARY
Includes one index entry for KEY VALUE
each block in the data file
The index entry has the key
ED

field value for the first record Aaron,
Adams, John

in the block, which is called
the block anchor
…
A similar scheme can use the
Wright, Pam

last record in a block
DATA FILE
PRIMARY
KEY FIELD
NAME
Aaron, ED
Abbott, Diane
OTHER ATTRIBUTES
….
….
Acosta, Marc
….
Adams, John
Adams, Robin
….
….
Akers, Jan
….
Wright, Pam
Wyatt, Charles
….
….
Zimmer, Byron ….
Update 2008
file-20
Single-Level Indexes – Clustering Index




Defined on an ordered
INDEX FILE
CLUSTERING BLOCK
data file
FIELD VALUE POINTER
The data file is ordered
on a non-key field
Includes one index
1


entry for each distinct 2
3

value of the field
4

The index entry points
…
to the first data block
that contains records
with that field value
Update 2008
CLUSTERING
FIELD
DEPTNUM
1
1
1
2
2
3
3
3
3
3
4
4
DATA FILE
OTHER
ATTRIBUTES
….
….
….
….
….
….
….
….
….
file-21
Single-Level Indexes - Secondary Index



INDEX FILE
BLOCK
POINTER
Defined on an
CLUSTERING
FIELD VALUE
unordered data file
Can be defined on a key
field or a non-key field 1
2
Includes one entry for 34
each record in the data
5
file; hence, it is called a 6
7
dense index
8
9
10
11
12
Update 2008












DATA FILE
INDEXING
FIELD
(secondary key
field)
8
3
7
6
….
….
12
2
5
9
….
….
1
11
10
4
….
….
….
….
file-22
Multi-Level Indexes

Because a single-level index is an ordered file, we
can create a primary index to the index itself





the original index file is called the first-level index
the index to the index is called the second-level index
We can repeat the process, creating a third, fourth,...,
top level until all entries of the top level fit in one
disk block
A multi-level index can be created for any type of
first-level index (primary, secondary, clustering) as
long as the first-level index consists of more than one
disk block
Such a multi-level index is a form of search tree;
however, insertion and deletion of new index entries
is a severe problem because every level of the index
is an ordered file
Update 2008
file-23
B-Trees and B+-Trees –
Dynamic Multi-level Indexes







These data structures are variations of search trees that allow
efficient insertion and deletion of new search values
In B-Tree and B+-Tree data structures, each node corresponds
to a disk block
Each node is kept between half-full and completely full
An insertion into a node that is not full is quite efficient; if a
node is full the insertion causes a split into two nodes
Splitting may propagate to other tree levels
A deletion is quite efficient if a node does not become less than
half full
If a deletion causes a node to become less than half full it
must be merged with neighboring nodes
Update 2008
file-24
Difference between B-tree and B+-tree



In a B-tree, pointers to data records exist at
all levels of the tree
In a B+-tree, all pointers to data records
exists at the leaf-level nodes
A B+-tree can have less levels (or higher
capacity of search values) than the
corresponding B-tree
Update 2008
file-25
B+-tree
(Knuth's variation)
50
82
index set
12
32
58
70
89
94
(nondense)
6
8 12
15 18 32
35 40 50
51 52 58
60 62 70
71 78 82
83 85 89
91 93 94
96 97 99
Sequence set
- index set: provides fast direct access to the sequential set
and thus to the data too.
- sequence set: provides fast sequential access to the indexed data.
(with pointers
to data records)
(dense or nondense)
 Other variations: B*-tree, B'-tree,...
Update 2008
file-26