Indexing

In Database
Agenda
Introduction 01
How it works 02
Advantages 03
Real world applications 04
Single-level Indexes 05
Multi- level Indexes 06
Other types 07
Issues Concerning 08
Indexing
Problems 09
 Introduction

Indexing in a database is a technique used to improve the speed of

data retrieval operations.
An index is essentially a data structure (often a B-tree or hash table)
that stores pointers to the actual rows in a database table

It allows the database management system (DBMS) to locate and

access data quickly without scanning the entire table.
improves Query Performance: Indexes make searching for records
faster by reducing the amount of data that needs to be scanned.
 How it works?
An index acts like a "lookup table," containing a
sorted list of values from one or more columns and
pointers (references) to the rows in the actual table.

When you create an index on a column the

database creates a separate data structure.
This data structure (often a B-tree or hash table)
is optimized for quick lookups.
The index stores the values of the indexed
column(s) in sorted order along with pointers to
the rows in the original table.
How it works?
 Example:

Product_id Product_name Category Price

1 Laptop Electronics 800

2 Smartphone Electronics 500

3 Microwave Oven Home Appliance 300

4 Headphones Electronics 100

5 Coffee Maker Home Appliance 80

 Example:

Scenario Without Indexing

Suppose you want to find all products in the Electronics category:

SQL
SELECT * FROM products WHERE category = 'Electronics';

Full Table Scan:

The database engine scans every row in the table to check if category =
'Electronics'.
For our example, it will check all five rows one by one.
For large tables (e.g., with millions of rows), this process is slow.
 Example:
Adding an Index on the category Column
To speed up queries, you create an index on the category column:

SQL
CREATE INDEX idx_category ON products(category);
What Happens Internally?
The database creates a separate data structure (usually a B-tree)
for the category column.
This structure stores all the unique values of the category column in
sorted order, along with pointers to the rows in the original table:

Electronics -> Rows 1, 2, 4

Home Appliance -> Rows 3, 5
 Example
Scenario With Indexing
Now, when you run the same query:
SQL

SELECT * FROM products WHERE category = 'Electronics';

1. Index Lookup:
Instead of scanning the entire table, the database engine looks up the value
Electronics in the index.
The index quickly identifies that Electronics corresponds to Rows 1, 2, and 4.
2. Pointer Access:
The engine uses the pointers in the index to directly retrieve the rows from
the products table.
 01 Faster Data Retrieval

02 Efficient Sorting

Advantages
03 Improved Performance for SELECT
Queries

04 Supports Unique Constraints

 Real world applications

E-commerce Platforms Banking and Financial Healthcare Systems

Systems
 Types of indexes
Single-Level Ordered Multilevel Indexes
Indexes
Multiple levels reduce search
Primary Index
space
Clustering Index
(e.g., B-Trees, B+-Trees).
Secondary Index

Other Types
Hash Indexes
Bitmap Indexes
Function-Based Indexes
Single-Level Ordered Indexes

Are structures that improve record retrieval

efficiency by organizing data in an ordered
manner, enabling quick access based on
indexing field values.
 Primary Index- Overview
Definition:
A primary index is specified on the ordering key field of an ordered file of
records.
The index helps locate records efficiently by maintaining their order.
Two Fields:
Key Value (K): Represents the search key.
Pointer (P): Points to the disk block containing records with the key
value.
Types:
Dense Index:
Contains an index entry for every search key value in the data file.
Sparse Index:
Contains entries for only some search key values, reducing storage
requirements.
 Primary Index- Challenges & Solutions

Challenges:
Insertion:
New records can disrupt the order, requiring adjustments to the index.
Deletion:
Removing records can lead to gaps in the file, affecting index accuracy.

Solutions:
Unordered Overflow File:
Use a separate file for overflow records to avoid reorganizing the main
file.
Linked List of Overflow Records:
Link overflow records to maintain order without physically moving them.
 Clustering Index :

Used when multiple records share the same value in the indexing field.

Records are physically ordered on a non-key field (not unique for every
record).

Structure:
Includes the clustering field and pointers to blocks where grouped
records are stored.

Dense or sparse?
Sparse index
distinct value
 Secondary Index

Provides an additional access path for fields that are not the ordering field.

Useful for improving search times for non-ordering attributes.

Structure:
Contains indexing fields and pointers to specific blocks or records.

Requires more storage space and can have longer search times
compared to primary indexes.
Dense or sparse?
Dense index
Multi-Level Ordered Indexes

Designed to greatly reduce remaining

search space as search is conducted,
if the size of the index is too big and can’t
be all uploaded in the memory
 Multi-Level Ordered Indexes

Index file Second level Third level

Considered Primary index Primary index
first to the first level to the second
(or base level) level
of a multilevel
index
 Note that:

Such a multi-level index is a form of search tree

 Problem

Insertion and deletion of new index entries is a severe problem

because every level of the index is an ordered file.

Designers adopted a multilevel index called a dynamic multilevel index

that leaves some space in each of its blocks for inserting new entries .

It uses appropriate insertion/deletion algorithms for creating and

deleting new index blocks when the data file , such as B-tree and B+ -tree
 Solution

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
Dynamic Multilevel Indexes
Using B-Trees and B+ -Trees

Tree is formed of nodes

Each node (except root) has one parent and zero or more
child nodes
Leaf node has no child nodes

Nonleaf node called internal node

Unbalanced if leaf nodes occur at different levels

Subtree of node consists of node and all descendant nodes

 Tree Data Structure

Figure 17.7 A tree data structure that shows an unbalanced tree

 A node in a Search Tree

Search tree used to guide search for a record

Given value of one of record’s fields:
 A Search Tree of order p=3
A search tree is slightly different from a multilevel index. A search tree
of order p is a tree such that each node contains at most p -1 search
values and p pointers
 B-Trees of order p
Provide multi-level access structure

Tree is always balanced(leaf nodes at the same level)

Every node contains multiple keys and have more than

two children
Each node is at least half-full , at least (p/2)-1 search values

Each node in a B-tree of order p can have at most p-1

search values
All search values in a node must be in ASC order

Space wasted by deletion never becomes excessive

 Example: B-Tree
B-Tree of Order p= 4

maximum search values: 3

minimum search values: 1 -->4/2-1=1
maximum children for a node / pointers: 4

B -Tree of order p= 5

maximum search values: 4

minimum search values: 1 -->5/2-1=1
maximum children for a node / pointers: 5
B-Tree Structures
 Example: B-Tree of order 4

maximum search values: 3

minimum search values: 1 -->4/2-1=1
maximum children for a node / pointers: 4
 Insertion of a search value in a B-Tree
1. Check whether tree is Empty.

2. If tree is Empty, then create a new node with new key value and insert it into the tree as a

root node.

3. If tree is Not Empty, then find the suitable leaf node to which the new key value is added

using Binary Search Tree logic

4. If that leaf node has empty position, add the new key value to that leaf node in ascending

order of key value within the node.

5. If that leaf node is already full, split that leaf node by sending middle value to its parent

node.

6. If the splitting is performed at root node then the middle value becomes new root node for

the tree and the height of the tree is increased by one.

Example: insert 8 to a B-Tree of order 5(splitting)

maximum search values: 4

node is full
 Deletion of a search value in a B-Tree(Merging)

1. Locate the leaf node.

2. If there are more than p/2 keys in the leaf node then delete the desired key
from the node.
3. If the leaf node doesn't contain p/2 keys then complete the keys by taking
the element from right or left sibling.
4. If the left sibling contains more than p/2 elements then push its largest
element up to its parent and move the intervening element down to the
node where the key is deleted.
 Deletion of a search value in a B-Tree(Merging)

5. If the right sibling contains more than p/2 elements then push its smallest

element up to the parent and move intervening element down to the node

where the key is deleted

6. If neither of the sibling contain more than p/2 elements then create a new

leaf node by joining two leaf nodes and the intervening element of the parent

node.

7. If parent is left with less than p/2 nodes then, apply the above process on the

parent too.
Example: Delete 53 from a B-Tree of order 5(Merging)

contains p/2
delete it

contains only one :merging

Example: Delete 53 from a B-Tree of order 5(Merging)

Rule 6
 B+ -Trees

B+ Tree is an extension of B Tree which allows

efficient insertion, deletion and search operations.
In B Tree, Keys and records both can be stored in the
internal as well as leaf nodes

In B+ tree, records (data) can only be stored on the

leaf nodes while internal nodes can only store the key
values.
The leaf nodes of a B+ tree are linked together in the
form of a singly linked lists to make the search
queries more efficient.
 B+ -Trees

Data pointers stored only at the leaf nodes:

Leaf nodes have an entry for every value of the search field, and
a data pointer to the record if search field is a key field
For a nonkey search field, the pointer points to a block
containing pointers to the data file records

Internal nodes:
Some search field values from the leaf nodes repeated
to guide search
B+ -Trees

Linked list
Rule 6
Rule 6
Rule 6
 Indexes on Multiple Keys

Multiple attributes involved in many retrieval and update

requests

Composite keys : Access structure using key value that

combines attributes

Partitioned hashing: Suitable for equality comparisons

 Indexes on Multiple Keys

Grid files: Array with one dimension for each search attribute
Hash indexes

Method used to map data to specific

locations in a hash table using a hash
function.
 Hash Index
Hash Function:
A mathematical function takes the value of a key (e.g., id or
username) and generates a unique hash value.

Hash Table:
The hash table stores the hash value as the key and a pointer to
the corresponding data in the database.
Key Lookup:
When a query is executed, the database applies the same hash
function to the search key and directly locates the corresponding
bucket in the hash table.
 Example

user_id name email

101 Alice alice@[Link]

102 Bob bob@[Link]

charlie@[Link]
103 Charlie
m
 Example
Hash Function: Assume the hash function maps the user_id modulo 10
101 % 10 = 1
102 % 10 = 2
103 % 10 = 3

Hash Table:
Index: 1 2 3
Value: Alice Bob Charlie

SQL:
SELECT * FROM users WHERE user_id = 102:

The hash function computes 102 % 10 = 2.

The database retrieves the record for user_id = 102 directly from index 2.
 Hash indexes

Advantages Disadvantages
Hash Collisions: Different
Fast Lookup
keys can produce the
Simple to Implement
same hash value
Efficient for Unique Keys.
(collision).

Performance Degradation
in Large Tables.
 Bitmap Indexes
Bitmap Indexes are a type of database index used to accelerate queries on
columns with a limited number of distinct values, such as columns with
repetitive or few values (low cardinality), like status (Active/Inactive) or gender
(Male/Female).

Bitmap Indexes work by representing the distinct values in a column using

bitmaps, where each value is represented by a bit array (0s and 1s). Each bit in
the array indicates whether a specific row contains that value.

Bitmap Indexes do not replace B-Tree Indexes but are used in specific cases
different from those where B-Tree Indexes are applied. Both can improve
database performance based on the data and query patterns.
 Key Differences:

Bitmap Indexes B-Tree Indexes

1. Suitable for columns with low 1. Suitable for columns with
cardinality. high cardinality.
2. Highly efficient for queries 2. Efficient for queries searching
involving multiple conditions for specific values or ranges
(AND/OR) across different (Range Queries).
columns. 3. Ideal for transactional
3. Best for analytical systems systems (OLTP) with frequent
(OLAP) where read-intensive insert, update, and delete
queries are common. operations.
 Why use them together?

Bitmap Indexes and B-Tree Indexes

1. Bitmap and B-Tree Indexes can coexist in the same

database to optimize performance based on column type
and query patterns.
2. In some cases, data with wide ranges can be transformed
into categorical values to make it more suitable for
Bitmap Indexes.
Function-Based Indexing

Value resulting from applying some

function on a field (or fields)
becomes the index key.
Introduced in Oracle relational DBMS
 Function-Based Indexing
Example:
Function:
UPPER(Lname) (converts last name to uppercase).

Query:
SELECT * FROM Employees
WHERE UPPER(Lname) = 'SMITH';

The function-based index speeds up execution.

Function-Based Indexing
Some General Issues Concerning Indexing

Physical Index: Logical Index:

Uses logical identifiers
Stores pointers to the
instead of physical
physical address of
pointers.
records.

Entries are in the form of

Disadvantage:
(K, Kp) where:
Needs updating if
K: Key value.
records are moved.
Kp: Pointer to the key or
record.
Some General Issues Concerning Indexing
Index Creation
General form of the command to create an index
Unique and cluster keywords optional
Order can be ASC or DESC

Secondary indexes can be created for any primary record

organization
Complements other primary access methods
Insertion of a large number of entries into the index is done by
a process called bulk loading
Some General Issues Concerning Indexing
Indexing of Strings
Strings can be variable length

Strings may be too long, limiting the fan-out

Prefix compression
Stores only the prefix of the search key adequate to
distinguish the keys that are being separated and directed
to the subtree
Some General Issues Concerning Indexing
Indexing of Strings
Stored inside index Text

Ahmed Ahmed

AhmedMohamed AhmedMohamed

Stored inside index Text

Ahmed Ahmed

Ahmed AhmedMohamed
Some General Issues Concerning Indexing
Tuning Indexes
Tuning Goals:
Dynamically evaluate indexing requirements.
Reorganize indexes for optimal performance.

Reasons for Tuning:

Certain queries may lack an index and run slowly.
Some indexes may not be utilized effectively.
High update rates may affect index performance
Additional Issues Related to Storage of Relations
and Indexes
Enforcing a key constraint on
an attribute Duplicates occur if index
Reject insertion if new is created on a nonkey
record has same key
attribute as existing
field
record
Fully inverted file
Has secondary index on every field
Indexing hints in queries
Suggestions used to expedite query
execution
Additional Issues Related to Storage of Relations
and Indexes
Column-based storage of relations
Alternative to traditional way of storing relations
by row
Offers advantages for read-only queries
Offers additional freedom in index creation
 Problems

Problem 01 Problem 02 Problem 03

Increased Slower Data

Additional
Storage Modification
Complexity
Requirements Operations
Any Questions?