Data Base Management Systems

UNIT V: Physical Database Design

Program & Semester: B.Tech & III SEM

Academic Year: 2023 - 24

Overview of Physical Storage

Cache

• The cache is the fastest and most costly form of storage.
• Cache memory is relatively small; cache effects when designing query processing data structures and algorithms.

Main memory.

• The storage medium used for data that are available to be operated on is main memory.
• The general-purpose machine instructions operate on main memory.
• Although main memory may contain several gigabytes of data on a personal computer, or even hundreds of gigabytes of data in large server systems, it is generally too small (or too expensive) for storing the entire database.

Flash memory.

• Flash memory differs from main memory in that stored data are retained even if power is turned off (or fails).
• There are two types of flash memory NAND and NOR flash has a much higher storage capacity for a given cost, and is widely used for data storage in devices such as cameras, music players, and cell phones. Of these, increasingly, in laptop computers as well.

Flash memory is also widely used for storing data in “USB keys,” which can be plugged into the Universal Serial Bus (USB) slots of computing devices.

Magnetic-disk storage

• The primary medium for the long-term online storage of data is the magnetic disk.
• Usually, the entire database is stored on magnetic disk. The system must move the data from disk to main memory so that they can be accessed.

Optical storage

• The most popular forms of optical storage are the compact disk (CD), and the digital video disk (DVD).
• The optical disks used in read-only compact disks (CD-ROM) or read-only digital video disks (DVD-ROM) cannot be written, but are supplied with data pre-recorded.
• There are also “record-once” versions of compact disk (called CD-R) and digital video disk (called DVD-R and DVD+R), which can be written only once.

Tape storage

Tape storage is used primarily for backup and archival data. Although magnetic tape is cheaper than disks, access to data is much slower, because the tape must be accessed sequentially from the beginning. For this reason, tape storage is referred to as sequential-access storage.

Magnetic Disk

Magnetic disks provide the bulk of secondary storage for modern computer

systems. A very large database may require hundreds of disks. In recent years, flash-memory storage sizes have grown rapidly, and flash storage is increasingly becoming a competitor to magnetic disk storage for several applications.

Physical Characteristics of Disks

Each disk platter has a flat, circular shape. Its two surfaces are covered with a magnetic material, and information is recorded on the surfaces.

There is a read–write head positioned just above the surface of the platter. The disk surface is logically divided into tracks, which are subdivided into sectors. A sector is the smallest unit of information that can be read from or written to the disk.

The read–write head stores information on a sector magnetically.

A disk typically contains many platters, and the read–write heads of all the tracks are mounted on a single assembly called a disk arm, and move together.

RAID (Redundant Arrays of Independent Disks)

• RAID, or “Redundant Arrays of Independent Disks” is a technique which makes use of a combination of multiple disks instead of using a single disk for increased performance, data redundancy or both.

​

• Data redundancy, although taking up extra space, adds to disk reliability. This means, in case of disk failure, if the same data is also backed up onto another disk, we can retrieve the data and go on with the operation.

​

• If the data is spread across just multiple disks without the RAID technique, the loss of a single disk can affect the entire data.
• RAID is very transparent to the underlying system.
• To the host system, it appears as a single big disk presenting itself as a linear array of blocks. This allows older technologies to be replaced by RAID without making too many changes in the existing code.
• RAID System is evaluated by Reliability, Availability, Performance, Capacity.
• There are 7 levels of RAID schemes. These schemas are as RAID 0, RAID 1, ...., RAID 6.

RAID-0 (Striping)

• RAID level 0 provides data stripping, i.e., a data can place across multiple disk.

​

​

​

​

​

​

​

• Instead of placing just one block into a disk at a time, we can work with two (or more) blocks placed into a disk before moving on to the next one.

​

​

2

Evaluation

Reliability: 0

• There is no duplication of data. Hence, a block once lost cannot be recovered.

Capacity: N*B

• The entire space is being used to store data. Since there is no duplication, N disks each having B blocks are fully utilized.

RAID-1 (Mirroring)

• More than one copy of each block is stored in a separate disk. Thus, every block has two (or more) copies, lying on different disks.

​

​

​

​

​

​

​

​

​

​

• The above figure shows a RAID-1 system with mirroring level 2.
• Every write of a disk block involves a write on both disks.
• RAID 0 was unable to tolerate any disk failure. But RAID 1 is capable of reliability.

​

Evaluation:

Assume a RAID system with mirroring level 2.

Reliability: 1 to N/2

• 1 disk failure can be handled for certain, because blocks of that disk would have duplicates on some other disk.
• If we are lucky enough and disks 0 and 2 fail, then again this can be handled as the blocks of these disks have duplicates on disks 1 and 3. So, in the best case, N/2 disk failures can be handled.

Capacity: N*B/2

• Only half the space is being used to store data. The other half is just a mirror to the already stored data.

RAID 2(Error- Correcting Code)

• RAID 2 consists of bit-level striping using hamming code parity.
• In this level, each data bit in a word is recorded on a separate disk and ECC (Error- Correcting Codes) of data words is stored on different set disks.
• Due to its high cost and complex structure, this level is not commercially used. The same performance can be achieved by RAID 3 at a lower cost.

​

​

​

​

​

​

​

​

​

Evaluation:

• This level uses one designated drive to store parity.
• It uses the hamming code for error detection.
• It requires an additional drive for error detection

​

RAID 3 (Byte-level striping )

• RAID 3 consists of byte-level striping with dedicated parity.
• In this level, the parity information is stored for each disk section and written to a dedicated parity drive.

​

• In case of drive failure, the parity drive is accessed, and data is reconstructed from the remaining devices. Once the failed drive is replaced, the missing data can be restored on the new drive.
• In this level, data can be transferred in bulk. Thus high-speed data transmission is possible.

​

​

​

​

​

​

​

Evaluation:

• In this level, data is regenerated using parity drive.
• It contains high data transfer rates.
• In this level, data is accessed in parallel.
• It required an additional drive for parity.
• It gives a slow performance for operating on small sized files.

​

RAID 4 (Block-Level Striping with Dedicated Parity)

Instead of duplicating data, this adopts a parity-based approach.

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

​

Parity is calculated using a simple XOR function. If the data bits are 0,0,0,1 the parity bit is XOR(0,0,0,1) = 1. If the data bits are 0,1,1,0 the parity bit is XOR(0,1,1,0) = 0. A simple approach is that even number of ones results in parity 0, and an odd number of ones results in parity 1.

​

​

​

Evaluation:

• Reliability: 1�RAID-4 allows recovery of at most 1 disk failure (because of the way parity works). If more than one disk fails, there is no way to recover the data.
• Capacity: (N-1)*B�One disk in the system is reserved for storing the parity. Hence, (N-1) disks are made available for data storage, each disk having B blocks.

RAID-5 (Block-Level Striping with Distributed Parity)

This is a slight modification of the RAID-4 system where the only difference is that the parity rotates among the drives.

​

​

​

​

​

​

​

This was introduced to make the random write performance better.

Evaluation:

Reliability: 1

• RAID-5 allows recovery of at most 1 disk failure (because of the way parity works). If more than one disk fails, there is no way to recover the data. This is identical to RAID-4.

Capacity: (N-1)*B

• Overall, space equivalent to one disk is utilized in storing the parity. Hence, (N-1) disks are made available for data storage, each disk having B blocks.

​

​

RAID-6 (Block-Level Striping with Dual Distributed Parity)

• This level is an extension of RAID 5. It contains block-level stripping with 2 parity bits.
• In RAID 6, you can survive 2 concurrent disk failures.
• RAID 6 plays its part where you can survive two concurrent disk failures before you run out of options

File Organization

A file is organized logically as a sequence of records. These records are mapped onto disk blocks.

• A page is collection of slots, each of which contains a record. Each page assigned an page id to identify in the File.
• A record is identified by using the pair (page id, slot number); this is the record id (rid). Alternative approaches to managing slots on a page
• In addition to the information about records on the page, a page usually contains additional file-level information.

​

Fixed-Length Records

• All records on the page are guaranteed to be of the same length, record slots arc uniform and can be arranged consecutively within a page.
• When a record is inserted into the page, we must locate an empty slot and place the record.
• For inserting a record into empty slot we must find where we have a empty slot it can be done in two ways
• The first alternative is to store records in the first N. whenever a record is deleted, we move the last record on the page into the vacated slot.
• This format allows us to locate the ith record on a page by a simple offset calculation, and all empty slots appear together at the end of the page.
• This approach docs not work if there are external references to the record

• The second alternative is to handle deletions by using an array of bits, one per slot, to keep track of free slot information.
• Locating records on the page requires scanning the bit array to find slots whose bit is on; when a record is deleted, its bit is turned off.

​

​

​

​

​

​

​

​

​

Variable-Length Records

• In variable length record type we cannot divide the page into a fixed collection of slots. The problem is that, when a new record is to be inserted, we have to find an empty slot of just the right length.
• When a record is deleted, we must move records to fill the hole created by the deletion, to ensure that all the free space on the page is contiguous

• The most flexible organization for variable-length records is to maintain a directory of slots for each page, with a (record offset (Location), record length(size)) pair per slot.
• The first component (record offset) is a 'pointer' to the record.
• Deletion is done by setting the record offset to -1.
• Records can be moved around on the page because the rid, which is the page number and slot number does not change when the record is moved; only the record offset stored in the slot changes.

​

RECORD FORMATS

• While choosing a way to organize the fields of a record, we must consider whether the fields of the record are of fixed or variable length and consider the cost of various operations on the record.
• Information common to all records of a given record type (such as the number of fields and field types) is stored in the system catalog, which can be thought of as a description of the contents of a database, maintained by the DBMS.

​

Fixed-Length Records

• In a fixed-length record, each field has a fixed length, and the number of fields is also fixed.
• The fields of such a record can be stored consecutively, and given the address of the record, the address of a particular field can be calculated using information about the lengths of preceding fields.

​

Variable-Length Records

• In the relational model, every record in a relation contains the same number of fields. If the number of fields is fixed, a record is of variable length only because some of its fields are of variable length.
• One possible organization is to store fields consecutively, separated by delimiters . This organization requires a scan of the record to locate a desired field.
• Another possible organization is to reserve some space at the beginning of a record for use as an array of integer offsets.
• The ith integer in this array is the starting address of the ith field value relative to the start of the record.
• we also store an offset to the end of the record; this offset is needed to recognize where the last held ends.

​

File Organization

A database consist of a huge amount of data. The data is grouped within a table in RDBMS, and each table have related records. A user can see that the data is stored in form of tables, but in actual this huge amount of data is stored in physical memory in form of files.

File : A file is named collection of related information that is recorded on secondary storage such as magnetic disks, magnetic tables and optical disks.

File Organization refers to the logical relationships among various records that constitute the file, particularly with respect to the means of identification and access to any specific record.

​

Types of File Organizations

• Sequential File Organization
• Heap File Organization
• Hash File Organization
• B+ Tree File Organization
• Clustered File Organization

Sequential File Organization

The easiest method for file Organization is Sequential method. In this method the file are stored one after another in a sequential manner. There are two ways to implement this method:

• Pile Method
• Sorted File Method

Pile Method

This method is quite simple, in which we store the records in a sequence i.e one after other in the order in which they are inserted into the tables

​

Advantages

• Fast and efficient method for huge amount of data.
• Simple design.
• Files can be easily stored in magnetic tapes i.e cheaper storage mechanism.

Disadvantages

• Time wastage as we cannot jump on a particular record that is required, but we must move in a sequential manner which takes our time.
• Sorted file method is inefficient as it takes time and space for sorting records.

​

Heap File Organization

​

• Heap File Organization works with data blocks.
• In this method records are inserted at the end of the file, into the data blocks.
• No Sorting or Ordering is required in this method.
• If a data block is full, the new record is stored in some other block, Here the other data block need not be the very next data block, but it can be any block in the memory.
• It is the responsibility of DBMS to store and manage the new records.

​

​

​

​

​

​

If a new block is inserted

​

​

Advantages

• Fetching and retrieving records is faster than sequential record but only in case of small databases.
• When there is a huge number of data needs to be loaded into the database at a time, then this method of file Organization is best suited.

Disadvantages

• Problem of unused memory blocks.
• Inefficient for larger databases.

​

​

Hash File Organization

• Hashing is an efficient technique to directly search the location of desired data on the disk without using index structure.
• Data is stored at the data blocks whose address is generated by using hash function.
• The memory location where these records are stored is called as data block or data bucket.

Data bucket

Data buckets are the memory locations where the records are stored. These buckets are also considered as Unit Of Storage.

Hash Function

• Hash function is a mapping function that maps all the set of search keys to actual record address.
• Generally, hash function uses primary key to generate the hash index.
• Hash function can be simple mathematical function to any complex mathematical function.

Hashing is further divided into two sub categories :

• Static Hashing
• Dynamic Hashing

Static Hashing

In static hashing, when a search-key value is provided, the hash function always computes the same address.

For example, if we want to generate address for STUDENT_ID = 76 using mod (5) hash function, it always result in the same bucket address 1. There will not be any changes to the bucket address here.

Hence number of data buckets in the memory for this static hashing remains constant throughout.

​

​

Insertion

When a new record is inserted into the table, The hash function h generate a bucket address for the new record based on its hash key K.

Bucket address = h(K)

Searching

When a record needs to be searched, The same hash function is used to retrieve the bucket address for the record.

If we want to retrieve whole record for ID 76, and if the hash function is mod (5) on that ID, the bucket address generated would be 1. Then we will directly got to address 1 and retrieve the whole record for ID 76. Here ID acts as a hash key.

Deletion

If we want to delete a record, Using the hash function we will first fetch the record which is supposed to be deleted. Then we will remove the records for that address in memory.

Updation

The data record that needs to be updated is first searched using hash function, and then the data record is updated.

When, we want to insert some new records into the file, but the data bucket address generated by the hash function is not empty or the data already exists in that address. This becomes a critical situation to handle. This situation in the static hashing is called bucket overflow.

• Open Hashing
• Closed hashing
• Quadratic probing
• Double Hashing

Open Hashing

Open hashing method, next available data block is used to enter the new record, instead of overwriting older one. This method is also called linear probing.

​

Closed hashing

In Closed hashing method, a new data bucket is allocated with same address and is linked it after the full data bucket. This method is also known as overflow chaining.

​

​

Quadratic probing

Quadratic probing is an open-addressing scheme where we look for i2‘th slot in i’th iteration if the given hash value x collides in the hash table.

How Quadratic Probing is done?

Let hash(x) be the slot index computed using the hash function.

If the slot hash(x) % S is full, then we try (hash(x) + 1*1) % S.

If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S.

If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S.

This process is repeated for all the values of i until an empty slot is found

​

Double hashing

Double hashing is a collision resolving technique in Open Addressed Hash tables. Double hashing uses the idea of applying a second hash function to key when a collision occurs.

​

Double hashing can be done using :

(hash1(key) + i * hash2(key)) % TABLE_SIZE

Here hash1() and hash2() are hash functions and TABLE_SIZE is size of hash table.

Dynamic Hashing

In Dynamic hashing, data buckets grows or shrinks (added or removed dynamically) as the records increases or decreases. Dynamic hashing is also known as extended hashing.

Extendible Hashing

Extendible Hashing is a dynamic hashing method where in directories, and buckets are used to hash data. It is an aggressively flexible method in which the hash function also experiences dynamic changes.

​

Directories

These containers store pointers to buckets. Each directory is given a unique id which may change each time when expansion takes place. The hash function returns this directory id which is used to navigate to the appropriate bucket. Number of Directories = 2^Global Depth.

Buckets

They store the hashed keys. Directories point to buckets. A bucket may contain more than one pointers to it if its local depth is less than the global depth.

Global Depth

It is associated with the Directories. They denote the number of bits which are used by the hash function to categorize the keys. Global Depth = Number of bits in directory id.

Local Depth

• It is the same as that of Global Depth except for the fact that Local Depth is associated with the buckets and not the directories.
• Local depth in accordance with the global depth is used to decide the action that to be performed in case an overflow occurs.
• Local Depth is always less than or equal to the Global Depth.

​

Bucket Splitting:

When the number of elements in a bucket exceeds a particular size, then the bucket is split into two parts.

Directory Expansion

Directory Expansion Takes place when a bucket overflows. Directory Expansion is performed when the local depth of the overflowing bucket is equal to the global depth.

Example of hashing the following elements: 16,4,6,22,24,10,31,7,9,20,26.

Bucket Size: 3 (Assume)

Hash Function: Suppose the global depth is X. Then the Hash Function returns X LSBs.

16- 10000 , 4- 00100 , 6- 00110 , 22- 10110 , 24- 11000 , 10- 01010 ,

31- 11111, 7- 00111, 9- 01001 , 20- 10100 , 26- 11010

The drawback of static hashing is that that it does not expand or shrink dynamically as the size of the database grows or shrinks

​

Dynamic Hashing

In Dynamic hashing, data buckets grows or shrinks as the records increases or decreases. Dynamic hashing is also known as extended hashing.

​

B+ Tree File Organization

B+ Tree, as the name suggests, It uses a tree like structure to store records in File. It uses the concept of Key indexing where the primary key is used to sort the records.

B+ Tree is very much like binary search tree, with the only difference that instead of just two children, it can have more than two.

All the information is stored in leaf node and the intermediate nodes acts as pointer to the leaf nodes.

The information in leaf nodes always remain a sorted sequential linked list.

​

Advantages

Tree traversal is easier and faster.

Searching becomes easy as all records are stored only in leaf nodes and are sorted sequential linked list.

There is no restriction on B+ tree size. It may grows/shrink as the size of data increases/decreases.

​

Disadvantages

Inefficient for static tables.

​

​

Cluster File Organization

In cluster file organization, two or more related tables/records are stored withing same file known as clusters.

These files will have two or more tables in the same data block and the key attributes which are used to map these table together are stored only once.

Thus it lowers the cost of searching and retrieving various records in different files as they are now combined and kept in a single cluster.

For example we have two tables or relation Employee and Department. These table are related to each other

These table are allowed to combine using a join operation and can be seen in a cluster file.

​

​

​

​

​

​

​

​

​

​

If we must insert, update or delete any record we can directly do so. Data is sorted based on the primary key or the key with which searching is done. Cluster key is the key with which joining of the table is performed.

​

There are two ways to implement this method:

• Indexed Clusters
• Hash Clusters

​

Indexed Clusters: 

In Indexed clustering the records are group based on the cluster key and stored together. The above example of the Employee and Department relationship is an example of Indexed Cluster where the records are based on the Department ID.

Hash Clusters:

This is very much similar to indexed cluster with only difference that instead of storing the records based on cluster key, we generate hash key value and store the records with same hash key value.

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

​

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

​

​

Comparison Of File Organizations:

Indexing

• Indexing is a way to optimize the performance of a database by minimizing the number of disk accesses required when a query is processed.
• It is a data structure technique which is used to quickly locate and access the data in a database.

Indexes are created using a few database columns.

The first column is the Search key that contains a copy of the primary key or candidate key of the table.

The second column is the Data Reference or Pointer which contains a set of pointers holding the address of the disk block where that particular key value can be found.

​

​

​

Classification Of Index

Dense Index

• For every search key value in the data file, there is an index record.
• This record contains the search key and also a reference to the first data record with that search key value.

�

​

​

​

​

​

​

​

​

​

​

​

Sparse Index

The index record appears only for a few items in the data file. Each item points to a block as shown.

​

Types of Indexing

1. Single-level Indexing

• Primary indexing
• Clustering Indexing
• Secondary Indexing

2. Multilevel Indexing

• B Trees
• B+ Trees

​

Primary indexing

It is defined mainly on the primary key of the data-file, in which the data-file is already ordered based on the primary key.

• Primary Index is an ordered file whose records are of fixed length with two fields. The first field of the index replicates the primary key of the data file in an ordered manner, and the second field of the ordered file contains a pointer that points to the data-block where a record containing the key is available.

​

• The first record of each block is called the Anchor record or Block anchor. There exists a record in the primary index file for every block of the data-file.
• The average number of blocks using the Primary Index is = log₂B + 1, where B is the number of index blocks.

​

Clustered index:

Clustered index is created only when both the following conditions satisfy

1. The data or file, that you are moving into secondary memory should be in sequential or sorted order. 
2. There should be non key value, meaning it can have repeated values. � 
1. Whenever you apply clustered indexing in a table, it will perform sorting in that table only. You can create only one clustered index in a table like primary key. Clustered index is as same as dictionary where the data is arranged by alphabetical order. 
2. In clustered index, index contains pointer to block but not direct data. 

​

Secondary Index or Non-clustered Index:

• The secondary Index in DBMS can be generated by a field which has a unique value for each record, and it should be a candidate key. It is also known as a non-clustering index.

​

Multilevel Indexing:

With the growth of the size of the database, indices also grow. As the index is stored in the main memory, a single-level index might become too large a size to store with multiple disk accesses. The multilevel indexing segregates the main block into various smaller blocks so that the same can stored in a single block. The outer blocks are divided into inner blocks which in turn are pointed to the data blocks. This can be easily stored in the main memory with fewer overheads.

B Tree

• B-Tree is a self-balancing search tree.
• 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.

​

Properties of B-Tree

• A B-Tree is defined by the term degree or Order ‘M’. The value of M depends upon disk block size.
• Every node in a B-Tree except the root node and the leaf node contain at least M/2 children.
• The root node must have at least 2 child nodes.
• All nodes (including root) may contain at most M – 1 keys.
• Every node in a B-Tree contains at most M children.
• All leaves are at the same level.
• All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.

A B tree of order 4 is shown below

​

​

​

​

​

​

​

​

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.

Operations

Searching

Insertion

Deletion

​

Searching

Searching in B Trees is like 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.

Insertion

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.

​

​

DELETION

• Deletion from a B-tree is more complicated than insertion, because we can delete a key from any node-not just a leaf.
• when we delete a key from an internal node, we will have to rearrange the node’s children.
• Just as we had to ensure that a node didn’t get too big due to insertion. we must ensure that a node doesn’t get too small during deletion.
• A simple approach to deletion might have to back up if a node (other than the root) along the path to where the key is to be deleted has the minimum number of keys.
• Since most of the keys in a B-tree are in the leaves, deletion operations are most often used to delete keys from leaves.
• The recursive delete procedure then acts in one downward pass through the tree, without having to back up.
• When deleting a key in an internal node, however, the procedure makes a downward pass through the tree but may have to return to the node from which the key was deleted to replace the key with its predecessor or successor.
• No of children must be according to the ceil of m/2.

​

​

After Deleting 6 the tree loos like

After deleting 13 the tree looks like

​

After deleting 7. Two leaf nodes are added to form the new node

For a B-Tree of order M

• Each internal node has up to M-1 keys to search
• Each internal node has between M/2 and M children
• Depth of B-Tree storing N items is O(log _M/2 N)

Run time is:

• O(log M) to binary search which branch to take at each node. But M is small compared to N.
• Total time to find an item is O(depth*log M) = O(log N)

​

The drawback of B-tree is that it stores the data pointer (a pointer to the disk file block containing the key value), corresponding to a particular key value, along with that key value in the node of a B-tree.

​

​

B+ tree

• B+ tree eliminates the above drawback by storing data pointers only at the leaf nodes of the tree.
• The structure of leaf nodes of a B+ tree is quite different from the structure of internal nodes of the B tree.
• The leaf nodes are linked to provide ordered access to the records.
• The leaf nodes form the first level of index, with the internal nodes forming the other levels of a multilevel index.
• Some of the key values of the leaf nodes also appear in the internal nodes, to simply act as a medium to control the searching of a record.
• B+ tree ‘a’ and ‘b’, one for the internal nodes and the other for the external (or leaf) nodes.

Internal Node structure

​

​

​

​

​

​

​

​

​

​

External Node (Leaf Node)

​

Using the Pnext pointer it is viable to traverse all the leaf nodes, just like a linked list, thereby achieving ordered access to the records stored in the disk.

​

​

​

​

​

​

​

​

​

​

​

​

A B+ tree with ‘l’ levels can store more entries in its internal nodes compared to a B-tree having the same ‘l’ levels. This accentuates the significant improvement made to the search time for any given key.

Operations on B+ Tree

• Searching.
• Insertion.
• Deletion.

Searching

• Searching just like in a binary search tree.
• Starts at the root, works down to the leaf level.
• Does a comparison of the search value and the current “separation value”, goes left or right.
• Since no structure change in a B+ tree during a searching process.
• So just compare the key value with the data in the tree, then give the result back.

Insertion

• A search is first performed, using the value to be added.
• After the search is completed, the location for the new value is known.
• If the tree is empty, add to the root.
• Once the root is full, split the data into 2 leaves, using the root to hold keys and pointers.
• If adding an element will overload a leaf, take the median and split it.

​

​

insert 28 into the below 5 ordered tree.

INSERTION

After inserting 28 the tree looks as below.

insert 70 into the below 5 ordered tree.

• While we are inserting the value 70 in leaf node 3 it exceeds the max number of keys (m-1).
• We need to split the leaf node by sending the mean value to the root
• After updating the tree looks as follows

​

Deletion

• Deletion, like insertion, begins with a search.
• When the item to be deleted is located and removed, the tree must be checked to make sure no rules are violated.
• The rule to focus on is to ensure that each node has at least ceil (n/2) pointers.

Example

Delete 60 from the below tree

• After deleting 60 from tree the rules specified for B+ tree are dissatisfied
• To make it again a B+ tree it should be rearranged as follows

​

​

​

​

​

​

​

The total time complexity of the B+ tree search operation is O(t log tn). Where O(t) is time complexity for each linear search.

The time complexity of the insertion algorithm is O(t log tn).

​

​

​

​

Advantages of B+ Trees:

1. Records can be fetched in equal number of disk accesses.
2. Height of the tree remains balanced and less compare to b-tree.
3. We can access the data stored in a B+ tree sequentially as well as directly.
4. Keys are used for indexing.
5. Faster search queries as the data is stored only on the leaf nodes.
6. Deletion will never be a complexed process since element will always be deleted from the leaf nodes in B+ trees .whereas in B tree, deletion of internal nodes are so complicated and time consuming.

​

Disadvantages of B+ Trees:

• Any search will end at leaf node only.
• Time complexity for every search results in O(h).
• Extra insertion and deletion overhead, space overhead..

​