ACID Properties of Transaction

This article is based on the concept of ACID properties in DBMS that are necessary for maintaining
data consistency, integrity, and reliability while performing transactions in the database. Let’s explore
them.

A transaction is a single logical unit of work that accesses and possibly modifies the contents of a
database. Transactions access data using read-and-write operations. To maintain consistency in a
database, before and after the transaction, certain properties are followed. These are
called ACID properties.

Atomicity:

By this, we mean that either the entire transaction takes place at once or doesn’t happen at all.
There is no midway i.e. transactions do not occur partially. Each transaction is considered as one unit
and either runs to completion or is not executed at all. It involves the following two operations.
— Abort : If a transaction aborts, changes made to the database are not visible.
— Commit : If a transaction commits, changes made are visible.
Atomicity is also known as the ‘All or nothing rule’.

Consider the following transaction T consisting of T1 and T2 : Transfer of 100 from account X to
account Y .
If the transaction fails after completion of T1 but before completion of T2 .( say, after write(X) but
before write(Y) ), then the amount has been deducted from X but not added to Y . This results in an
inconsistent database state. Therefore, the transaction must be executed in its entirety in order to
ensure the correctness of the database state.

Consistency:

This means that integrity constraints must be maintained so that the database is consistent before
and after the transaction. It refers to the correctness of a database. Referring to the example above,
The total amount before and after the transaction must be maintained.
Total before T occurs = 500 + 200 = 700 .
Total after T occurs = 400 + 300 = 700 .
Therefore, the database is consistent . Inconsistency occurs in case T1 completes but T2 fails. As a
result, T is incomplete.

Isolation:

This property ensures that multiple transactions can occur concurrently without leading to the
inconsistency of the database state. Transactions occur independently without interference. Changes
occurring in a particular transaction will not be visible to any other transaction until that particular
change in that transaction is written to memory or has been committed. This property ensures that
the execution of transactions concurrently will result in a state that is equivalent to a state achieved
these were executed serially in some order.
Let X = 500, Y = 500.
Consider two transactions T and T”.

Suppose T has been executed till Read (Y) and then T’’ starts. As a result, interleaving of operations
takes place due to which T’’ reads the correct value of X but the incorrect value of Y and sum
computed by
T’’: (X+Y = 50, 000+500=50, 500)
is thus not consistent with the sum at end of the transaction:
T: (X+Y = 50, 000 + 450 = 50, 450) .
This results in database inconsistency, due to a loss of 50 units. Hence, transactions must take place
in isolation and changes should be visible only after they have been made to the main memory.
Durability:

This property ensures that once the transaction has completed execution, the updates and
modifications to the database are stored in and written to disk and they persist even if a system
failure occurs. These updates now become permanent and are stored in non-volatile memory. The
effects of the transaction, thus, are never lost.

Transaction States in DBMS

Transaction in DBMS is a set of logically related operations executed as a single unit. These logic are
followed to perform modification on data while maintaining integrity and consistency. Transactions
are performed in a way that concurrent actions from different users don’t malfunction the database.
Transfer of money from one account to another in a bank management system is the best example of
Transaction.

States through which a transaction goes during its lifetime. These are the states which tell about the
current state of the Transaction and also tell how we will further do the processing in the
transactions. These states govern the rules which decide the fate of the transaction whether it will be
committed or aborted. They also use a Transaction log.

Transaction States in DBMS

A Transaction log is a file maintained by the recovery management component to record all the
activities of the transaction. After the commit is done transaction log file is removed.

In DBMS, a transaction passes through various states such as active, partially committed, failed, and
aborted. Understanding these transaction states is crucial for database management and ensuring
the consistency of data.
These are different types of Transaction States :

1. Active State – When the instructions of the transaction are running then the transaction is in
active state. If all the ‘read and write’ operations are performed without any error then it goes to the
“partially committed state”; if any instruction fails, it goes to the “failed state”.

2. Partially Committed – After completion of all the read and write operation the changes are made
in main memory or local buffer. If the changes are made permanent on the DataBase then the state
will change to “committed state” and in case of failure it will go to the “failed state”.

3. Failed State – When any instruction of the transaction fails, it goes to the “failed state” or if failure
occurs in making a permanent change of data on Database.

4. Aborted State – After having any type of failure the transaction goes from “failed state” to
“aborted state” and since in previous states, the changes are only made to local buffer or main
memory and hence these changes are deleted or rolled-back.

[Link] State – It is the state when the changes are made permanent on the Data Base and the
transaction is complete and therefore terminated in the “terminated state”.

[Link] State – If there isn’t any roll-back or the transaction comes from the “committed
state”, then the system is consistent and ready for new transaction and the old transaction is
terminated.

Concurrent Execution of Transactions

Concurrent execution refers to the simultaneous execution of more than one transaction. This is a
common scenario in multi-user database environments where many users or applications might be
accessing or modifying the database at the same time. Concurrent execution is crucial for achieving
high throughput and efficient resource utilization. However, it introduces the potential for conflicts
and data inconsistencies.

Advantages of Concurrent Execution

1. Increased System Throughput: Multiple transactions can be in progress at the same time,
but at different stages

2. Maximized Processor Utilization: If one transaction is waiting for I/O operations, another
transaction can utilize the processor.

3. Decreased Wait Time: Transactions no longer have to wait for other long transactions to
complete.

4. Improved Transaction Response Time: Transactions get processed faster because they can
be executed in parallel.

Potential Problems with Concurrent Execution

1. Lost Update Problem (Write-Write conflict):

One transaction's updates could be overwritten by another.

Examples:

T1 | T2

----------|-----------

Read(A) |

A = A+50 |

| Read(A)

| A = A+100

Write(A) |

| Write(A)

Result: T1's updates are lost.

[Link] Inconsistency or Dirty Read Problem (Write-Read conflict):

One transaction might read an inconsistent state of data that's being updated by another.

Examples:

T1 | T2

------------------|-----------

Read(A) |

A = A+50 |

Write(A) |

| Read(A)

| A = A+100

| Write(A)

Read(A)(rollbacks)|

| commit
Result: T2 has a "dirty" value, that was never committed in T1 and doesn't actually exist in the
database.

3. Unrepeatable Read Problem (Read-Write conflict):

when a single transaction reads the same row multiple times and observes different values each
time. This occurs because another concurrent transaction has modified the row between the two
reads.

Examples:

T1 | T2

----------|----------

Read(A) |

| Read(A)

| A = A+100

| Write(A)

Read(A) |

Result: Within the same transaction, T1 has read two different values for the same data item. This
inconsistency is the unrepeatable read.

To manage concurrent execution and ensure the consistency and reliability of the database, DBMSs
use concurrency control techniques. These typically include locking mechanisms, timestamps,
optimistic concurrency control, and serializability checks.

Types of Schedules in DBMS

Schedule, as the name suggests, is a process of lining the transactions and executing them one by
one. When there are multiple transactions that are running in a concurrent manner and the order of
operation is needed to be set so that the operations do not overlap each other, Scheduling is brought
into play and the transactions are timed accordingly.
Schedules in DBMS ensure that transactions are executed in a serializable order. Understanding the
types of schedules is crucial for ensuring database consistency.

Serial Schedules: Schedules in which the transactions are executed non-interleaved, i.e., a serial
schedule is one in which no transaction starts until a running transaction has ended are called serial
schedules. Example: Consider the following schedule involving two transactions T 1 and T 2 .

T1 T2

R(A)

W(A)

R(B)

W(B)

R(A)

R(B)
1. where R(A) denotes that a read operation is performed on some data item ‘A’ This is a serial
schedule since the transactions perform serially in the order T 1 —> T 2

1. Non-Serial Schedule: This is a type of Scheduling where the operations of multiple

transactions are interleaved. This might lead to a rise in the concurrency problem.
The transactions are executed in a non-serial manner, keeping the end result correct
and same as the serial schedule. Unlike the serial schedule where one transaction
must wait for another to complete all its operation, in the non-serial schedule, the
other transaction proceeds without waiting for the previous transaction to complete.

2. Serializable: This is used to maintain the consistency of the database. It is mainly

used in the Non-Serial scheduling to verify whether the scheduling will lead to any
inconsistency or not. On the other hand, a serial schedule does not need the
serializability because it follows a transaction only when the previous transaction is
complete. The non-serial schedule is said to be in a serializable schedule only when it
is equivalent to the serial schedules, for an n number of transactions. Since
concurrency is allowed in this case thus, multiple transactions can execute
concurrently. A serializable schedule helps in improving both resource utilization and
CPU throughput. These are of two types:

1. Conflict Serializable: A schedule is called conflict serializable if it can be

transformed into a serial schedule by swapping non-conflicting operations.
Two operations are said to be conflicting if all conditions satisfy:

 They belong to different transactions

 They operate on the same data item

 At Least one of them is a write operation

2. View Serializable: A Schedule is called view serializable if it is view equal to a

serial schedule (no overlapping transactions). A conflict schedule is a view
serializable but if the serializability contains blind writes, then the view
serializable does not conflict serializable.

2. Non-Serializable: The non-serializable schedule is divided into two types,

Recoverable and Non-recoverable Schedule.

1. Recoverable Schedule: Schedules in which transactions commit only after all

transactions whose changes they read commit are called recoverable
schedules. In other words, if some transaction T j is reading value updated or
written by some other transaction T i , then the commit of T j must occur
after the commit of T i . Example – Consider the following schedule involving
two transactions T 1 and T 2 .
 T1 T2

R(A)

W(A)

W(A)

R(A)

commit

commit

2. This is a recoverable schedule since T 1 commits before T 2 , that makes the

value read by T 2 correct.

Lock-Based Protocol

In this type of protocol, any transaction cannot read or write data until it acquires an appropriate
lock on it. There are two types of lock:

1. Shared lock:

o It is also known as a Read-only lock. In a shared lock, the data item can only read by the
transaction.

o It can be shared between the transactions because when the transaction holds a lock, then it
can't update the data on the data item.

2. Exclusive lock:

o In the exclusive lock, the data item can be both reads as well as written by the transaction.

o This lock is exclusive, and in this lock, multiple transactions do not modify the same data
simultaneously.

Two-phase locking (2PL)

o The two-phase locking protocol divides the execution phase of the transaction into three
parts.
 o In the first part, when the execution of the transaction starts, it seeks permission for the lock
it requires.

o In the second part, the transaction acquires all the locks. The third phase is started as soon
as the transaction releases its first lock.

o In the third phase, the transaction cannot demand any new locks. It only releases the
acquired locks.

There are two phases of 2PL:

Growing phase: In the growing phase, a new lock on the data item may be acquired by the
transaction, but none can be released.

Shrinking phase: In the shrinking phase, existing lock held by the transaction may be released, but no
new locks can be acquired.

In the below example, if lock conversion is allowed then the following phase can happen:

1. Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.

2. Downgrading of lock (from X(a) to S(a)) must be done in shrinking phase.

Example:

The following way shows how unlocking and locking work with 2-PL.

Transaction T1:

o Growing phase: from step 1-3

o Shrinking phase: from step 5-7

o Lock point: at 3

Transaction T2:

o Growing phase: from step 2-6

o Shrinking phase: from step 8-9

o Lock point: at 6
Timestamp Based Protocol

o The Timestamp Ordering Protocol is used to order the transactions based on their
Timestamps. The order of transaction is nothing but the ascending order of the transaction
creation.

o The priority of the older transaction is higher that's why it executes first. To determine the
timestamp of the transaction, this protocol uses system time or logical counter.

o The lock-based protocol is used to manage the order between conflicting pairs among
transactions at the execution time. But Timestamp based protocols start working as soon as
a transaction is created.

o Let's assume there are two transactions T1 and T2. Suppose the transaction T1 has entered
the system at 007 times and transaction T2 has entered the system at 009 times. T1 has the
higher priority, so it executes first as it is entered the system first.

o The timestamp ordering protocol also maintains the timestamp of last 'read' and 'write'
operation on a data.

Basic Timestamp ordering protocol works as follows:

1. Check the following condition whenever a transaction Ti issues a Read (X) operation:

o If W_TS(X) >TS(Ti) then the operation is rejected.

o If W_TS(X) <= TS(Ti) then the operation is executed.

o Timestamps of all the data items are updated.

2. Check the following condition whenever a transaction Ti issues a Write(X) operation:

o If TS(Ti) < R_TS(X) then the operation is rejected.

o If TS(Ti) < W_TS(X) then the operation is rejected and Ti is rolled back otherwise the
operation is executed.

Indexing in DBMS
o Indexing is used to optimize the performance of a database by minimizing the number of
disk accesses required when a query is processed.

o The index is a type of data structure. It is used to locate and access the data in a database
table quickly.

Index structure:

Indexes can be created using some database columns.

 o The first column of the database is the search key that contains a copy of the primary key or
candidate key of the table. The values of the primary key are stored in sorted order so that
the corresponding data can be accessed easily.

o The second column of the database is the data reference. It contains a set of pointers holding
the address of the disk block where the value of the particular key can be found.

Indexing Methods

Ordered indices

The indices are usually sorted to make searching faster. The indices which are sorted are known as
ordered indices.

Example: Suppose we have an employee table with thousands of record and each of which is 10
bytes long. If their IDs start with 1, 2, 3....and so on and we have to search student with ID-543.

o In the case of a database with no index, we have to search the disk block from starting till it
reaches 543. The DBMS will read the record after reading 543*10=5430 bytes.

o In the case of an index, we will search using indexes and the DBMS will read the record after
reading 542*2= 1084 bytes which are very less compared to the previous case.

Primary Index

o If the index is created on the basis of the primary key of the table, then it is known as
primary indexing. These primary keys are unique to each record and contain 1:1 relation
between the records.
 o As primary keys are stored in sorted order, the performance of the searching operation is
quite efficient.

o The primary index can be classified into two types: Dense index and Sparse index.

Dense index

o The dense index contains an index record for every search key value in the data file. It makes
searching faster.

o In this, the number of records in the index table is same as the number of records in the
main table.

o It needs more space to store index record itself. The index records have the search key and a
pointer to the actual record on the disk.

Sparse index

o In the data file, index record appears only for a few items. Each item points to a block.

o In this, instead of pointing to each record in the main table, the index points to the records in
the main table in a gap.

Clustering Index

o A clustered index can be defined as an ordered data file. Sometimes the index is created on
non-primary key columns which may not be unique for each record.

o In this case, to identify the record faster, we will group two or more columns to get the
unique value and create index out of them. This method is called a clustering index.

o The records which have similar characteristics are grouped, and indexes are created for these
group.

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

The previous schema is little confusing because one disk block is shared by records which belong to
the different cluster. If we use separate disk block for separate clusters, then it is called better
technique.
Secondary Index

In the sparse indexing, as the size of the table grows, the size of mapping also grows. These mappings
are usually kept in the primary memory so that address fetch should be faster. Then the secondary
memory searches the actual data based on the address got from mapping. If the mapping size grows
then fetching the address itself becomes slower. In this case, the sparse index will not be efficient. To
overcome this problem, secondary indexing is introduced.

In secondary indexing, to reduce the size of mapping, another level of indexing is introduced. In this
method, the huge range for the columns is selected initially so that the mapping size of the first level
becomes small. Then each range is further divided into smaller ranges. The mapping of the first level
is stored in the primary memory, so that address fetch is faster. The mapping of the second level and
actual data are stored in the secondary memory (hard disk).
Index data Structures

One way to organize data entries is to hash data entries on the [Link] key. Another way to organize
data entries is to build a tree-like data structure that directs a search for data entries.

Hash-Based Indexing

In hash-based indexing, a hash function is used to convert a key into a hash code. This hash code
serves as an index where the value associated with that key is stored. The goal is to distribute the
keys uniformly across an array, so that access time is, on average, constant.

Let's break down some of these elements to further understand how hash-based indexing works in
practice:

Buckets

In hash-based indexing, the data space is divided into a fixed number of slots known as "buckets." A
bucket usually contains a single page (also known as a block), but it may have additional pages linked
in a chain if the primary page becomes full. This is known as overflow.
Hash Function

The hash function is a mapping function that takes the search key as an input and returns the bucket
number where the record should be located. Hash functions aim to distribute records uniformly
across buckets to minimize the number of collisions (two different keys hashing to the same bucket).

Disk I/O Efficiency

Hash-based indexing is particularly efficient when it comes to disk I/O operations. Given a search key,
the hash function quickly identifies the bucket (and thereby the disk page) where the desired record
is located. This often requires only one or two disk I/Os, making the retrieval process very fast.

Insert Operations

When a new record is inserted into the dataset, its search key is hashed to find the appropriate
bucket. If the primary page of the bucket is full, an additional overflow page is allocated and linked to
the primary page. The new record is then stored on this overflow page.

Search Operations

To find a record with a specific search key, the hash function is applied to the search key to identify
the bucket. All pages (primary and overflow) in that bucket are then examined to find the desired
record.

Limitations

Hash-based indexing is not suitable for range queries or when the search key is not known. In such
cases, a full scan of all pages is required, which is resource-intensive.

Hash-Based Indexing Example

Let's consider a simple example using employee names as the search key.

Employee Records

| Name | Age | Salary

|-----------|----------|--------

| Alice | 28 | 50000

| Bob | 35 | 60000

| Carol | 40 | 70000

Hash Function: H(x) = ASCII value of first letter of the name mod 3

 Alice: 65 mod 3 = 2

 Bob: 66 mod 3 = 0

 Carol: 67 mod 3 = 1
Buckets:

Bucket 0: Bob
Bucket 1: Carol
Bucket 2: Alice

Pros of Hash-Based Indexing

 Extremely fast for exact match queries.

 Well-suited for equality comparisons.

Cons of Hash-Based Indexing

 Not suitable for range queries (e.g., "SELECT * FROM table WHERE age BETWEEN 20 AND
30").

 Performance can be severely affected by poor hash functions or a large number of collisions.

Tree-based Indexing

The most commonly used tree-based index structure is the B-Tree, and its variations like B+ Trees
and B* Trees. In tree-based indexing, data is organized into a tree-like structure. Each node
represents a range of key values, and leaf nodes contain the actual data or pointers to the data.

Why Tree-based Indexing?

Tree-based indexes like B-Trees offer a number of advantages:

 Sorted Data: They maintain data in sorted order, making it easier to perform range queries.

 Balanced Tree: B-Trees and their variants are balanced, meaning the path from the root
node to any leaf node is of the same length. This balancing ensures that data retrieval times
are consistently fast, even as the dataset grows.

 Multi-level Index: Tree-based indexes can be multi-level, which helps to minimize the
number of disk I/Os required to find an item.

 Dynamic Nature: B-Trees are dynamic, meaning they're good at inserting and deleting
records without requiring full reorganization.

 Versatility: They are useful for both exact-match and range queries.

Tree-based Indexing Example

Continuing with the "Students" table:

ID Name

1 Abhi

2 Bharath

3 Chinni

4 Devid
A simplified B-Tree index could look like this:

[1, 3]

/ \

[1] [3, 4]

/ \ / \

1 2 3 4

In the tree, navigating from the root to the leaf nodes will lead us to the desired data record.

Pros of Tree-based Indexing:

 Efficient for range queries.

 Good for both exact and partial matches.

 Keeps data sorted.

Cons of Tree-based Indexing:

 Slower than hash-based indexing for exact queries.

 More complex to implement and maintain.

Comparison of File Organizations, Indexes and Performance Tuning

File organization, indexing, and performance tuning are three interconnected areas in the realm of
Database Management Systems, each contributing to the overall efficiency and effectiveness of data
storage and retrieval. Below is a comparison of these three concepts, focusing on their objectives,
methodologies, and implications.

File Organizations

1. Objective: To physically store records on storage media in an organized manner.

2. Methodologies: Includes sequential, random (or direct), and hashed file organizations, among
others.

3. Implications:

 Sequential organization is suitable for batch processing but inefficient for random access.

 Direct or random organization allows fast access but can be inefficient in terms of storage
space.

 Hashed file organization is excellent for equality searches but not for range-based queries.

4. Real-world Examples: Ledger systems, log files, archival systems.

Indexing

1. Objective: To create a data structure that improves the speed of data retrieval operations.

2. Methodologies: Includes clustered, non-clustered, primary, secondary, composite, bitmap, and

hash indexes, among others.

3. Implications:

 Clustered indexes are excellent for range-based queries but slow down insert/update
operations.

 Non-clustered indexes improve data retrieval speed but can take up additional storage.

 Bitmap indexes are useful for low-cardinality columns.

4. Real-world Examples: Search engines, e-commerce websites, any application that requires fast
data retrieval.

Performance Tuning

1. Objective: To optimize the resources used by the database for efficient transaction processing.

2. Methodologies: Query optimization, index tuning, denormalization, database sharding, caching,

partitioning, etc.

3. Implications:

 Query optimization can dramatically reduce the resources needed for query processing.

 Proper indexing can mitigate the need for full-table scans.

 Denormalization and caching can improve read operations but may compromise data
integrity or consistency.

4. Real-world Examples: Financial trading systems, real-time analytics, high-performance computing.

Points of Comparison on File organization, indexing, and performance tuning

1. Granularity:

 File organization is about how data is stored at the file level.

 Indexing is about improving data access at the table or even column level.

 Performance tuning is a broad set of activities that can encompass both file organization and
indexing among many other techniques.

2. Resource Usage:

 File organization techniques aim to use disk space efficiently.

 Indexing aims to use both disk space and memory for fast data retrieval.

 Performance tuning aims to optimize all system resources including CPU, memory, disk, and
network bandwidth.
3. Query Efficiency:

 File organization generally impacts how efficiently data can be read or written to disk.

 Indexing significantly impacts how efficiently queries can retrieve data.

 Performance tuning seeks to optimize both read and write operations through a variety of
methods.

4. Complexity:

 File organization is relatively straightforward.

 Indexing can become complex depending on the types of indexes and the nature of the
queries.

 Performance tuning is usually the most complex as it involves a holistic understanding of

hardware, software, data, and queries.

Dynamic Index Structure - B+ Tree

what is A Dynamic Index Structure

A dynamic index structure is an index that automatically adjusts its structure as the underlying data
grows, shrinks, or otherwise changes. Unlike static index structures, which are fixed in size and
organization, dynamic index structures reorganize themselves in response to changes in the data
they index. This makes them more flexible and scalable, capable of handling varying workloads and
data distributions efficiently.

Dynamic index structures are crucial for databases that are expected to evolve over time, especially
when it comes to insertion, deletion, and updating of records. They maintain balanced tree
structures, self-adjust, and optimize, ensuring that the database operations remain efficient even as
the data grows or changes.

Examples of Dynamic Index Structures:

B-Trees and B+-Trees: These are perhaps the most well-known examples of dynamic index structures.
B-Trees and B+-Trees automatically split or merge nodes to maintain a balanced tree, ensuring that
search, insert, and delete operations take logarithmic time. They are widely used in various types of
databases and filesystems.

Introduction of B+ Tree

B + Tree is a variation of the B-tree data structure. In a B + tree, data pointers are stored only at the
leaf nodes of the tree. In a B+ tree structure of a leaf node differs from the structure of internal
nodes. The leaf nodes have an entry for every value of the search field, along with a data pointer to
the record (or to the block that contains this record). The leaf nodes of the B+ tree are linked
together to provide ordered access to the search field to the records. Internal nodes of a B+ tree are
used to guide the search. Some search field values from the leaf nodes are repeated in the internal
nodes of the B+ tree.

Features of B+ Trees
  Balanced: B+ Trees are self-balancing, which means that as data is added or removed from
the tree, it automatically adjusts itself to maintain a balanced structure. This ensures that the
search time remains relatively constant, regardless of the size of the tree.

 Multi-level: B+ Trees are multi-level data structures, with a root node at the top and one or
more levels of internal nodes below it. The leaf nodes at the bottom level contain the actual
data.

 Ordered: B+ Trees maintain the order of the keys in the tree, which makes it easy to perform
range queries and other operations that require sorted data.

 Fan-out: B+ Trees have a high fan-out, which means that each node can have many child
nodes. This reduces the height of the tree and increases the efficiency of searching and
indexing operations.

 Cache-friendly: B+ Trees are designed to be cache-friendly, which means that they can take
advantage of the caching mechanisms in modern computer architectures to improve
performance.

 Disk-oriented: B+ Trees are often used for disk-based storage systems because they are
efficient at storing and retrieving data from disk.

Why Use B+ Tree?

 B+ Trees are the best choice for storage systems with sluggish data access because they
minimize I/O operations while facilitating efficient disc access.

 B+ Trees are a good choice for database systems and applications needing quick data
retrieval because of their balanced structure, which guarantees predictable performance for
a variety of activities and facilitates effective range-based queries.

Difference Between B+ Tree and B Tree

Some differences between B+ Tree and B Tree are stated below.

Parameters B+ Tree B Tree

Separate leaf nodes for data storage

Structure Nodes store both keys and data values
and internal nodes for indexing

Leaf nodes form a linked list for

Leaf Nodes Leaf nodes do not form a linked list
efficient range-based queries

Order Higher order (more keys) Lower order (fewer keys)

Parameters B+ Tree B Tree

Key Typically allows key duplication in leaf

Usually does not allow key duplication
Duplication nodes

Better disk access due to sequential More disk I/O due to non-sequential
Disk Access
reads in a linked list structure reads in internal nodes

Database systems, file systems, In-memory data structures, databases,

Applications
where range queries are common general-purpose use

Better performance for range queries Balanced performance for search,

Performance
and bulk data retrieval insert, and delete operations

Memory Requires more memory for internal Requires less memory as keys and
Usage nodes values are stored in the same node