1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

B+ Tree Index Structure (order=3):
 
                        ┌─────────────┐
                        │   [30,60]   │              (Root Node)
                        └──────┬──────┘
               ┌───────────────┼───────────────┐
               ▼               ▼               ▼
        ┌───────────┐   ┌───────────┐   ┌───────────┐
        │ [10,20]   │   │ [40,50]   │   │ [70,80]   │  (Internal Nodes)
        └─────┬─────┘   └─────┬─────┘   └─────┬─────┘
         ┌────┼────┐     ┌────┼────┐     ┌────┼────┐
         ▼    ▼    ▼     ▼    ▼    ▼     ▼    ▼    ▼
       ┌───┐┌───┐┌───┐ ┌───┐┌───┐┌───┐ ┌───┐┌───┐┌───┐
       │5,8││15 ││25,│ │35,││45 ││55,│ │65,││75 ││85,│ (Leaf Nodes)
       │   ││18 ││28 │ │38 ││48 ││58 │ │68 ││78 ││90 │
       └─┬─┘└─┬─┘└─┬─┘ └─┬─┘└─┬─┘└─┬─┘ └─┬─┘└─┬─┘└─┬─┘
         │    │    │     │    │    │     │    │    │
         ▼    ▼    ▼     ▼    ▼    ▼     ▼    ▼    ▼
      [Row][Row][Row] [Row][Row][Row] [Row][Row][Row]  (Data Pages/Row Pointers)
 
Key Properties:
1. All data pointers are in leaf nodes only
2. Leaf nodes are linked for sequential access (→→→)
3. Internal nodes only guide the search
4. Tree is always balanced (all leaves at same level)
 
Search for key=45:
  Root: 45 ≥ 30 and 45 < 60, go middle
  Internal: 45 ≥ 40 and 45 < 50, go middle  
  Leaf: Found! Return row pointer
 
Disk reads: 3 (one per level) - regardless of table size!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

-- B-tree index (default)
CREATE INDEX idx_customer_email ON Customer(email);
 
-- Composite index (multiple columns)
CREATE INDEX idx_order_customer_date ON Order(customer_id, order_date);
-- Efficient for: WHERE customer_id = ? AND order_date = ?
-- Also efficient for: WHERE customer_id = ? (leftmost prefix)
-- NOT efficient for: WHERE order_date = ? (not leftmost)
 
-- Unique index (also enforces constraint)
CREATE UNIQUE INDEX idx_product_sku ON Product(sku);
 
-- Partial index (only index rows matching condition)
CREATE INDEX idx_active_orders ON Order(order_date)
WHERE status = 'active';
-- Smaller index, faster for common queries
 
-- Covering index (includes all columns needed by query)
CREATE INDEX idx_order_covering ON Order(customer_id)
INCLUDE (order_date, total_amount, status);
-- Query can be answered from index alone, no table access needed
 
-- Hash index (PostgreSQL)
CREATE INDEX idx_customer_id_hash ON Customer USING HASH(customer_id);
-- Slightly faster equality lookups, no range support
 
-- GIN index for full-text search
CREATE INDEX idx_product_search ON Product 
USING GIN(to_tsvector('english', product_name || ' ' || description));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

Typical Database Page Structure (8KB example):
 
┌────────────────────────────────────────────────────────────────┐
│ Page Header (24-100 bytes)                                     │
│ ┌────────────┬────────────┬────────────┬────────────────────┐ │
│ │ Page ID    │ LSN        │ Checksum   │ Free Space Pointer │ │
│ │ [4 bytes]  │ [8 bytes]  │ [4 bytes]  │ [2 bytes]          │ │
│ └────────────┴────────────┴────────────┴────────────────────┘ │
├────────────────────────────────────────────────────────────────┤
│ Item Pointers (Line Pointer Array) - grows downward            │
│ ┌────────┬────────┬────────┬────────┬────────┬───────────┐    │
│ │ Ptr 1  │ Ptr 2  │ Ptr 3  │ Ptr 4  │ Ptr 5  │ ...       │    │
│ │ →Row1  │ →Row2  │ →Row3  │ →Row4  │ →Row5  │           │    │
│ └────────┴────────┴────────┴────────┴────────┴───────────┘    │
│                              ↓                                  │
│ ╔════════════════════════════════════════════════════════════╗ │
│ ║              F R E E   S P A C E                           ║ │
│ ║                                                            ║ │
│ ╚════════════════════════════════════════════════════════════╝ │
│                              ↑                                  │
├────────────────────────────────────────────────────────────────┤
│ Tuple Data (Row Data) - grows upward from bottom               │
│ ┌───────────────────────────────────────────────────────────┐ │
│ │ Row 5: customer_id=105, name='Eve Garcia', email=...      │ │
│ ├───────────────────────────────────────────────────────────┤ │
│ │ Row 4: customer_id=104, name='David Lee', email=...       │ │
│ ├───────────────────────────────────────────────────────────┤ │
│ │ Row 3: customer_id=103, name='Carol White', email=...     │ │
│ ├───────────────────────────────────────────────────────────┤ │
│ │ Row 2: customer_id=102, name='Bob Jones', email=...       │ │
│ ├───────────────────────────────────────────────────────────┤ │
│ │ Row 1: customer_id=101, name='Alice Smith', email=...     │ │
│ └───────────────────────────────────────────────────────────┘ │
└────────────────────────────────────────────────────────────────┘
 
Key Design Elements:
1. Item pointers allow rows to move within page (for compaction)
2. Free space between pointers and data allows efficient insertion
3. Header contains page metadata for recovery and integrity
4. Fixed page size enables efficient I/O and buffer management

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

-- Create tablespace on specific storage
-- PostgreSQL example
CREATE TABLESPACE fast_ssd LOCATION '/mnt/nvme/pg_data';
CREATE TABLESPACE archive_hdd LOCATION '/mnt/hdd/pg_archive';
 
-- Create table on specific tablespace
CREATE TABLE hot_data (
    id SERIAL PRIMARY KEY,
    data JSONB,
    created_at TIMESTAMP DEFAULT NOW()
) TABLESPACE fast_ssd;
 
CREATE TABLE cold_archive (
    id BIGINT PRIMARY KEY,
    data JSONB,
    archived_at TIMESTAMP
) TABLESPACE archive_hdd;
 
-- Move existing table to different tablespace
ALTER TABLE order_history SET TABLESPACE archive_hdd;
 
-- Create index on different tablespace than table
CREATE INDEX idx_hot_data_created 
ON hot_data(created_at) 
TABLESPACE fast_ssd;
 
-- Oracle: Create tablespace with specific parameters
-- CREATE TABLESPACE sales_data
--   DATAFILE '/u01/oradata/sales01.dbf' SIZE 10G
--   EXTENT MANAGEMENT LOCAL
--   SEGMENT SPACE MANAGEMENT AUTO;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

-- PostgreSQL: Check buffer cache hit ratio
SELECT 
    sum(blks_hit) / nullif(sum(blks_hit + blks_read), 0) * 100 AS cache_hit_ratio
FROM pg_stat_database;
-- Goal: > 99% cache hit ratio for OLTP workloads
 
-- PostgreSQL: See what's in the buffer cache (requires pg_buffercache extension)
CREATE EXTENSION pg_buffercache;
 
SELECT 
    c.relname AS table_name,
    count(*) AS buffers,
    round(100.0 * count(*) / (SELECT count(*) FROM pg_buffercache WHERE relfilenode IS NOT NULL), 2) AS percent_of_cache
FROM pg_class c
JOIN pg_buffercache b ON b.relfilenode = pg_relation_filenode(c.oid)
GROUP BY c.relname
ORDER BY buffers DESC
LIMIT 20;
 
-- MySQL: InnoDB buffer pool statistics
SHOW STATUS LIKE 'Innodb_buffer_pool%';
-- Key metrics: 
-- Innodb_buffer_pool_read_requests (logical reads)
-- Innodb_buffer_pool_reads (physical reads from disk)
-- Hit ratio = 1 - (reads / read_requests)
 
-- MySQL: Buffer pool contents summary
SELECT 
    TABLE_NAME,
    ENGINE,
    TABLE_ROWS,
    ROUND(DATA_LENGTH / 1024 / 1024, 2) AS data_mb,
    ROUND(INDEX_LENGTH / 1024 / 1024, 2) AS index_mb
FROM information_schema.TABLES
WHERE TABLE_SCHEMA = 'your_database'
ORDER BY DATA_LENGTH DESC;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

-- Partitioning by date range (PostgreSQL)
CREATE TABLE order_history (
    order_id        BIGINT,
    order_date      DATE NOT NULL,
    customer_id     INTEGER,
    total_amount    DECIMAL(12,2)
) PARTITION BY RANGE (order_date);
 
CREATE TABLE order_history_2023 PARTITION OF order_history
    FOR VALUES FROM ('2023-01-01') TO ('2024-01-01');
    
CREATE TABLE order_history_2024 PARTITION OF order_history
    FOR VALUES FROM ('2024-01-01') TO ('2025-01-01');
 
-- Query only scans relevant partition
SELECT * FROM order_history WHERE order_date = '2024-06-15';
-- Only order_history_2024 is accessed!
 
-- Compression (PostgreSQL TOAST + external compression)
-- Large values automatically compressed and stored out-of-line
 
-- MySQL InnoDB compression
ALTER TABLE archive_data ROW_FORMAT=COMPRESSED KEY_BLOCK_SIZE=8;
 
-- Fill factor (PostgreSQL)
CREATE INDEX idx_product_name ON product(name) WITH (fillfactor = 70);
-- Leaves 30% free space per page for updates
 
-- Clustered table (PostgreSQL)
CLUSTER order_history USING idx_order_date;
-- Physically reorders rows by order_date - one-time operation
 
-- Oracle IOT (Index-Organized Table) - data stored in index structure
-- CREATE TABLE hot_data (
--     id NUMBER PRIMARY KEY,
--     data VARCHAR2(100)
-- ) ORGANIZATION INDEX;