Hashing & B+ Trees

// DIVISION METHOD: h(k) = k mod N  (N = number of buckets)
// Simple and fast. Best when N is a prime not close to a power of 2.
h(42)  = 42 mod 10 = 2   → bucket 2
h(52)  = 52 mod 10 = 2   → bucket 2 (COLLISION — same bucket as 42)
h(73)  = 73 mod 10 = 3   → bucket 3

// PROBLEM with division: if keys cluster (e.g., all end in 0), one bucket fills up.
// N should be prime to reduce clustering patterns.

// MULTIPLICATION METHOD: h(k) = floor(N × (k × A mod 1))
// A = (√5 - 1)/2 ≈ 0.618 (golden ratio) — produces excellent distribution
// More complex to compute but avoids clustering for common key patterns.

// STRING HASHING — polynomial rolling hash:
h("C042") = (ord('C') × 31³ + ord('0') × 31² + ord('4') × 31 + ord('2')) mod N
// Different characters → different hash values
// Order-sensitive: "C042" and "C024" hash differently

// UNIVERSALLY UNIQUE HASH (for distributed systems):
// MurmurHash3, FNV-1a, xxHash — designed for speed and excellent distribution
// Used in PostgreSQL's internal hashing (e.g., hash joins, hash indexes)

// KEY PROPERTY TO REMEMBER:
// Hash functions DESTROY ORDER information.
// h(30) and h(31) have no mathematical relationship.
// This is why hash indexes cannot be used for range queries (>, <, BETWEEN).
// Only B+ trees preserve order and support range scans.

// SEARCH for key k:
bucket = h(k)           // compute bucket number
page = bucket_directory[bucket]  // get the disk page for this bucket
while page != null:
    for each (key, ptr) in page:
        if key == k: return ptr  // found!
    page = page.overflow_next    // follow overflow chain
return NOT_FOUND

// Average case: O(1) if no overflow, O(overflow_chain_length) with overflow
// Worst case: O(n) if all keys hash to same bucket (terrible hash function)

// INSERT key k with row pointer ptr:
bucket = h(k)
page = bucket_directory[bucket]
if page has free slot:
    add (k, ptr) to page
    write page to disk
else:
    // bucket is full — allocate overflow page
    new_page = allocate_new_disk_page()
    add (k, ptr) to new_page
    page.overflow_next = new_page
    write both pages to disk

// DELETE key k:
bucket = h(k)
page = bucket_directory[bucket]
while page != null:
    if k in page:
        remove (k, ptr) from page
        if page is empty and is overflow page:
            // optionally reclaim the overflow page
            unlink page from overflow chain
        return SUCCESS
    page = page.overflow_next
return NOT_FOUND

// THE FUNDAMENTAL PROBLEM WITH STATIC HASHING:
// As data grows, overflow chains grow, and lookup cost degrades.
// As data shrinks, buckets are mostly empty — wasted space.
// N is fixed at creation — cannot adapt to changing data volumes.
// Solution: Dynamic hashing (Extendible or Linear hashing).

// SETUP: bucket capacity = 2 entries, h(k) uses binary representation of k

// STATE 0: global_depth=1, 2 directory entries, 2 buckets, both local_depth=1
// Directory:
//   0 → Bucket A (local_depth=1): empty
//   1 → Bucket B (local_depth=1): empty

// INSERT k=2 (binary: 10, last bit = 0 → Bucket A):
// Directory[0] → Bucket A: [2]

// INSERT k=4 (binary: 100, last bit = 0 → Bucket A):
// Directory[0] → Bucket A: [2, 4]  ← Bucket A is now FULL (capacity=2)

// INSERT k=6 (binary: 110, last bit = 0 → Bucket A):
// Bucket A is full → SPLIT required

// SPLIT PROCEDURE for Bucket A (local_depth=1, global_depth=1):
// local_depth == global_depth → must DOUBLE THE DIRECTORY first

// STEP 1: Double the directory (global_depth: 1 → 2)
// Old directory (depth=1):    New directory (depth=2):
//   bit[0]: 0 → Bucket A        bit[1:0]: 00 → Bucket A (unchanged)
//   bit[0]: 1 → Bucket B        bit[1:0]: 01 → Bucket B (unchanged)
//                                bit[1:0]: 10 → Bucket A (SAME as 00 for now)
//                                bit[1:0]: 11 → Bucket B (SAME as 01 for now)
// After doubling: 4 directory entries, but still only 2 actual buckets

// STEP 2: Create new Bucket A' and redistribute Bucket A's keys
// Bucket A had: [2, 4]
// New bit to distinguish: bit[1] (second bit from right)
// k=2: binary 010, bit[1]=1 → Bucket A' (new)
// k=4: binary 100, bit[1]=0 → Bucket A  (original, renamed)
// k=6: binary 110, bit[1]=1 → Bucket A' (new)

// STEP 3: Update directory pointers
// bit[1:0]=00 → Bucket A  (local_depth=2): [4]
// bit[1:0]=01 → Bucket B  (local_depth=1): []
// bit[1:0]=10 → Bucket A' (local_depth=2): [2, 6]
// bit[1:0]=11 → Bucket B  (local_depth=1): []

// STATE after inserting 2, 4, 6:
// Global depth = 2, directory = [00→A, 01→B, 10→A', 11→B]
// Bucket A  (local_depth=2): [4]
// Bucket A' (local_depth=2): [2, 6]
// Bucket B  (local_depth=1): []

// INSERT k=1 (binary: 001, last 2 bits = 01 → Bucket B):
// Bucket B: [1]

// INSERT k=3 (binary: 011, last 2 bits = 11 → Bucket B):
// Bucket B: [1, 3]  ← full

// INSERT k=5 (binary: 101, last 2 bits = 01 → Bucket B):
// Bucket B is full → SPLIT
// local_depth(B) = 1 < global_depth = 2 → NO directory doubling needed!
// Create Bucket B', redistribute by bit[1]:
// k=1: binary 001, bit[1]=0 → Bucket B
// k=3: binary 011, bit[1]=1 → Bucket B'
// k=5: binary 101, bit[1]=0 → Bucket B
// Update directory: 01 → Bucket B (local_depth=2): [1,5]
//                   11 → Bucket B' (local_depth=2): [3]

// FINAL STATE:
// Global depth = 2
// Directory: 00→A [4], 01→B [1,5], 10→A' [2,6], 11→B' [3]
// All buckets have local_depth = 2

// SEARCH for k=6:
// h(6) = 110, last 2 bits = 10 → directory[10] → Bucket A' → find 6 ✓
// COST: 1 directory lookup + 1 bucket page read = 2 operations (near O(1))

// LINEAR HASHING STATE:
// n     = current number of buckets
// sp    = split pointer (which bucket splits next, starts at 0)
// level = current level (how many times n has doubled, starts at 0)

// TWO HASH FUNCTIONS:
// h_level(k)   = k mod (2^level × n₀)         // current level hash
// h_level+1(k) = k mod (2^(level+1) × n₀)     // next level hash (twice as many buckets)
// n₀ = initial number of buckets (e.g., 2)

// WHICH HASH FUNCTION TO USE FOR A GIVEN KEY:
// Compute h_level(k)
// If h_level(k) < sp (bucket has already been split this round):
//     use h_level+1(k)  ← use next-level hash for already-split buckets
// Else:
//     use h_level(k)   ← use current hash for not-yet-split buckets

// INSERT TRIGGER: when load factor > threshold (e.g., 0.75 full):
// 1. Split bucket at sp (regardless of which bucket overflowed)
// 2. Create new bucket at position n + sp
// 3. Redistribute keys in bucket[sp] between bucket[sp] and new bucket
//    using h_level+1(k): keys where h_level+1(k) = sp stay in bucket[sp]
//                        keys where h_level+1(k) = sp + old_n go to new bucket
// 4. sp++ (advance split pointer)
// 5. If sp == old_n: level++, sp = 0, n = 2 × old_n (completed one round)

// ─────────────────────────────────────────────────────────────────
// WORKED EXAMPLE: n₀=2, bucket capacity=3, h_level(k) = k mod 2
// ─────────────────────────────────────────────────────────────────

// Initial state: level=0, sp=0, n=2
// h₀(k) = k mod 2
// Bucket 0: []  Bucket 1: []

// INSERT 4,8,2,12,6 (all even → all hash to bucket 0 via k mod 2)
// After 4: Bucket 0: [4]
// After 8: Bucket 0: [4,8]
// After 2: Bucket 0: [4,8,2]  ← full (capacity=3)
// INSERT 12: would overflow bucket 0 → TRIGGER SPLIT at sp=0

// SPLIT bucket[0]:
// Create bucket[2] (= n + sp = 2 + 0)
// Use h₁(k) = k mod 4 to redistribute bucket[0]=[4,8,2]:
//   h₁(4)=0  → stays in bucket[0]
//   h₁(8)=0  → stays in bucket[0]
//   h₁(2)=2  → moves to bucket[2]
// sp = 1, n = 3

// State: level=0, sp=1, n=3
// Bucket 0: [4,8]  Bucket 1: []  Bucket 2: [2]
// Now INSERT 12: h₀(12)=0, but 0 < sp=1 → use h₁(12)=12 mod 4=0
//   bucket[0]=[4,8,12]  ← full again already!

// INSERT 6: h₀(6)=0, 0 < sp=1 → h₁(6)=6 mod 4=2 → bucket[2]=[2,6]
// INSERT 5: h₀(5)=1, 1 >= sp=1 → h₀(5)=1 → bucket[1]=[5]
// INSERT 11: overflow trigger → SPLIT bucket[sp=1]:
// Create bucket[3] (= 3 + 1)
// Use h₁(k) = k mod 4 to redistribute bucket[1]=[5]:
//   h₁(5)=1 → stays in bucket[1]
// sp=2 now equals old_n=2? No, old_n was 2, sp=2 → YES, round complete
// level=1, sp=0, n=4, h_level = k mod 4 now

// SEARCH for k in linear hashing:
// h_current(k) = k mod (2^level × n₀)
// if result < sp: use h_next(k) = k mod (2^(level+1) × n₀)
// Look in that bucket (+ overflow chain if exists)
// Cost: O(1) average if overflow chains are short

// ASSUMPTIONS:
// Page size = 8KB = 8192 bytes
// Key size = 8 bytes (64-bit integer)
// Data pointer = 8 bytes (row ID)
// Child pointer = 8 bytes (page number)

// B-TREE internal node:
// Each entry: [child_ptr | key | data_ptr] = 8+8+8 = 24 bytes
// Plus one extra child pointer at end
// Fan-out = (8192 - 8) / 24 ≈ 341 children per internal node

// B+ TREE internal node (keys only, no data pointers):
// Each entry: [child_ptr | key] = 8+8 = 16 bytes
// Plus one extra child pointer at end
// Fan-out = (8192 - 8) / 16 ≈ 511 children per internal node

// TREE HEIGHT COMPARISON for 50 million records:
// B-tree  height: ceil(log₃₄₁(50,000,000)) ≈ ceil(3.44) = 4 levels
// B+ tree height: ceil(log₅₁₁(50,000,000)) ≈ ceil(3.14) = 4 levels
// (similar at this scale)

// But for 50 BILLION records:
// B-tree  height: ceil(log₃₄₁(50,000,000,000)) ≈ ceil(5.98) = 6 levels
// B+ tree height: ceil(log₅₁₁(50,000,000,000)) ≈ ceil(5.69) = 6 levels

// More importantly: RANGE QUERY difference
// "Find all orders from Jan 2024" — 100,000 matching rows
// B-tree:  traverse tree for each matching row → 100,000 × O(log n) lookups
//          OR traverse in-order which requires going up and down the tree
// B+ tree: find first Jan 2024 leaf via tree traversal (O(log n) = 4 reads)
//          follow linked list through 100K matching leaf entries (sequential reads)
//          Total: 4 random reads + N sequential leaf page reads
//          Sequential reads are 4-10x faster than random reads on spinning disk

// THE DEFINITIVE REASON DATABASES USE B+ TREES:
// Range scans (WHERE date BETWEEN x AND y, ORDER BY col, etc.) are extremely common
// in database workloads. B+ tree's linked leaf list makes range scans as fast as
// a sequential scan of just the matching portion — without reading the entire table.

// EXACT SEARCH for key k in B+ tree:
node = root
while node is not a leaf:
    i = index such that key[i] <= k < key[i+1]
    node = child[i+1]   // follow the appropriate child pointer
// Now at a leaf node:
if k in node.keys:
    return node.pointer_for(k)  // found — follow pointer to actual row
else:
    return NOT_FOUND

// EXAMPLE: Search for k=45 in a tree of order 4
// Root: [20 | 40 | 60]  (3 keys → 4 children)
// 45 > 40 and 45 < 60 → follow third child pointer
// Internal node: [42 | 46]
// 45 > 42 and 45 < 46 → follow second child pointer
// Leaf node: [43 | 45 | 45*]
// 45 found! Follow pointer to row.

// RANGE SEARCH for k BETWEEN a AND b:
// Step 1: Search for a (exact search reaching a leaf)
node = leaf containing first key >= a
// Step 2: Follow linked list forward collecting all keys <= b
result = []
while node != null and node.keys.min <= b:
    for key in node.keys:
        if a <= key <= b:
            result.append(key)
    node = node.next_leaf  // follow linked list right pointer
return result

// COST: O(log_n(N)) tree traversal + O(k/capacity) leaf page reads
// k = number of matching keys, capacity = keys per leaf page
// This is optimal — no wasted reads of non-matching data

// B+ TREE of ORDER 4 (max 3 keys per node, max 4 children per internal node)
// Min keys: internal nodes ≥ ⌈4/2⌉-1 = 1 key, leaf nodes ≥ ⌈3/2⌉ = 2 keys

// INITIAL STATE:
//                 [30 | 70]
//               /     |     //     [10|20]  [40|50|60]  [80|90]
// All are leaf nodes, linked: [10|20] ↔ [40|50|60] ↔ [80|90]

// INSERT k=25:
// Search: 25 < 30 → first child → leaf [10|20]
// Leaf [10|20] has room → insert in sorted order
// Leaf becomes [10|20|25]  ✓ (capacity 3, now full)

// INSERT k=35:
// Search: 30 < 35 < 70 → middle child → leaf [40|50|60]
// 35 < 40 → wait, 35 < 40 but we're in this leaf... actually:
// The separator 30 means: keys in left subtree < 30
// 30 ≤ 35 < 70 → middle child → leaf [40|50|60]
// Hmm, 35 < 40. This should go in the leaf that contains values between 30 and 40.
// Actually in a B+ tree the key 30 in the parent means:
// Left child ≤ 30, middle child between 30 and 70
// 35 ≥ 30 → middle child
// Middle leaf [40|50|60] is full (3 keys) → SPLIT

// LEAF SPLIT of [40|50|60] when inserting 35:
// Temporary: [35|40|50|60] (4 keys — overflow, then split)
// Left new leaf:  [35|40]
// Right new leaf: [50|60]
// Push COPY of first key in right leaf up to parent: push up 50
// Parent was: [30|70], becomes [30|50|70]
// Update leaf linked list: [10|20|25] ↔ [35|40] ↔ [50|60] ↔ [80|90]

// INSERT k=15:
// 15 < 30 → left leaf [10|20|25]
// Leaf is FULL (3 keys) → SPLIT
// Temporary: [10|15|20|25]
// Left leaf:  [10|15]
// Right leaf: [20|25]
// Push copy of 20 up to parent
// Parent was: [30|50|70], becomes [20|30|50|70] — 4 keys → OVERFLOW

// INTERNAL NODE SPLIT of [20|30|50|70]:
// This is the root (or parent internal node)
// Split: left internal node [20|30], right internal node [50|70]
// Middle key 50? Wait — for internal nodes the MIDDLE key is PUSHED UP (not copied)
// Keys: [20|30|50|70]
// Middle = 50 → push 50 up
// Left internal:  [20|30] with appropriate children
// Right internal: [70] with appropriate children
// If this was the root: create new root [50] with left and right as children
// Tree height increases by 1

// KEY RULE FOR SPLITS:
// LEAF split: copy the first key of the right half up to parent (key stays in leaf too)
// INTERNAL split: push the middle key up to parent (key is REMOVED from the split node)

// FINAL STATE (after all insertions):
//               [50]
//              /    //         [20|30]   [70]
//        /   |       |   // [10|15] [20|25] [35|40] [50|60] [80|90]

// DELETION ALGORITHM:
// 1. Find the leaf containing the key
// 2. Remove the key from the leaf
// 3. If leaf still has >= minimum keys: done (update parent separator if needed)
// 4. If leaf has < minimum keys: UNDERFLOW
//    a. Try to borrow from left sibling (redistribution)
//    b. Try to borrow from right sibling (redistribution)
//    c. If neither works: merge with a sibling

// ─────────────────────────────────────────────────────────────────
// EXAMPLE TREE (order 4, min keys in leaf = 2):
//            [30 | 70]
//           /    |    //    [10|20] [40|50|60] [80|90]
// ─────────────────────────────────────────────────────────────────

// DELETE k=60:
// Leaf [40|50|60] → remove 60 → [40|50]
// Still has 2 keys (minimum) → NO UNDERFLOW → done ✓
//            [30 | 70]
//           /    |    //    [10|20] [40|50] [80|90]

// DELETE k=10:
// Leaf [10|20] → remove 10 → [20]
// Only 1 key < minimum (2) → UNDERFLOW

// CHECK LEFT SIBLING: none (leftmost leaf)
// CHECK RIGHT SIBLING: [40|50] → has 2 keys = minimum → cannot borrow
//   (borrowing would leave sibling with 1 key, also below minimum)

// MERGE: merge [20] with right sibling [40|50]
// Merged leaf: [20|40|50]
// Remove separator key 30 from parent (30 separated these two leaves)
// Parent becomes [70]

// UPDATE LEAF LIST: remove the merged-in leaf from the chain

// PARENT [70] now has only 1 key and 2 children — is this valid?
// Root node: minimum is 1 key (root can have as few as 1 key and 2 children)
// So [70] as root is valid ✓

// FINAL STATE:
//         [70]
//        /    // [20|40|50] [80|90]

// ─────────────────────────────────────────────────────────────────
// DELETE WITH REDISTRIBUTION EXAMPLE:
// ─────────────────────────────────────────────────────────────────
// Tree (order 4):
//          [50]
//         /    //   [20|30|40] [60|70]

// DELETE k=60:
// Leaf [60|70] → remove 60 → [70]
// Only 1 key < minimum (2) → UNDERFLOW
// LEFT SIBLING [20|30|40] has 3 keys > minimum → CAN BORROW

// REDISTRIBUTION (borrow from left sibling):
// Move the LARGEST key from left sibling (40) to the underflowing leaf
// Underflowing leaf becomes [40|70]
// Update separator in parent: was 50, now becomes 40
//   (50 was the boundary between left and right; now 40 is the boundary)

// FINAL STATE:
//          [40]
//         /    //   [20|30] [40|70]   ← wait, 40 appears in both parent and right leaf
// In B+ tree: leaf contains 40 (it's actual data), parent contains copy as separator
// This is correct! Parent's 40 means: left subtree < 40, right subtree >= 40
// [20|30] < 40 ✓, [40|70] >= 40 ✓

// KEY REDISTRIBUTION RULES:
// Borrow from LEFT sibling:
//   → move largest key from left sibling to start of underflowing leaf
//   → update parent separator to be the new smallest key of the right leaf
// Borrow from RIGHT sibling:
//   → move smallest key from right sibling to end of underflowing leaf
//   → update parent separator to be the new smallest key of the right sibling

// BULK LOADING ALGORITHM:

// Step 1: Sort all N key-pointer pairs by key
// Cost: O(N log N) for external sort
// After sort: [1,ptr] [2,ptr] [4,ptr] [7,ptr] [8,ptr] [10,ptr] [12,ptr] ...

// Step 2: Fill leaf pages to ~67% capacity (leave room for future inserts)
// Why 67%? Inserting into a nearly-full tree causes immediate splits.
// Pre-loading to 67% gives ~33% free space for growth before first split.
// Fill factor is configurable: CREATE INDEX ... WITH (fillfactor=70)

// Create leaf pages in order:
// Leaf 1: [1 | 2 | 4]      (3 keys at ~67% of capacity-4 leaf)
// Leaf 2: [7 | 8 | 10]
// Leaf 3: [12 | 15 | 18]
// Leaf 4: [20 | 25]        (last leaf, partially filled)
// Link leaves: L1 ↔ L2 ↔ L3 ↔ L4

// Step 3: Build internal nodes using FIRST KEY of each leaf (except the first)
// First key of L2 = 7, L3 = 12, L4 = 20
// Create internal node: [7 | 12 | 20]  → 4 children (3 keys, 4 pointers)
// If more leaves exist than fit one internal node: recurse upward

// Step 4: If multiple internal nodes created, build the next level
// Continue until only one node remains → that is the root

// RESULT: fully-built B+ tree in O(N log N) time
// (dominated by the sort step; tree construction is O(N))

// POSTGRESQL BULK LOADING (happens automatically during CREATE INDEX):
CREATE INDEX idx_orders_date ON orders(order_date);
-- PostgreSQL sorts the column values (using work_mem for in-memory sort)
-- Then builds the B+ tree bottom-up using the bulk loading algorithm
-- This is why CREATE INDEX is faster than inserting rows one at a time

-- FILL FACTOR control:
CREATE INDEX idx_orders_date ON orders(order_date) WITH (fillfactor = 70);
-- Leaves filled to 70% during bulk load
-- Leaves: more free space for inserts → fewer splits
-- Trade-off: slightly larger index (more pages) but better write performance

The payments table receives 50,000 inserts per second and must support these query patterns:

CREATE TABLE payments (
    payment_id   UUID          PRIMARY KEY DEFAULT gen_random_uuid(),
    merchant_id  VARCHAR(30)   NOT NULL,
    api_key      VARCHAR(64)   NOT NULL,
    amount       DECIMAL(15,2) NOT NULL,
    currency     CHAR(3)       NOT NULL DEFAULT 'INR',
    status       VARCHAR(20)   NOT NULL DEFAULT 'created',
    created_at   TIMESTAMP     NOT NULL DEFAULT CURRENT_TIMESTAMP,
    completed_at TIMESTAMP
);

-- Q1: Primary key B+ tree index — created automatically
-- (payment_id is the clustered index in PostgreSQL via CLUSTER, or implicit in MySQL InnoDB)

-- Q2: Hash index for pure equality API key lookups
CREATE INDEX idx_payments_apikey ON payments USING HASH(api_key);

-- Q3: Composite B+ tree for merchant + date range queries
CREATE INDEX idx_payments_merchant_date ON payments(merchant_id, created_at DESC);

-- Q4: Partial B+ tree for failed payments only
CREATE INDEX idx_payments_failed ON payments(created_at DESC)
WHERE status = 'failed';

-- BULK LOAD CONSIDERATION:
-- When loading historical payment data (100M rows):
-- 1. Load data with no indexes except PRIMARY KEY
-- 2. After load completes:
CREATE INDEX CONCURRENTLY idx_payments_apikey ON payments USING HASH(api_key);
CREATE INDEX CONCURRENTLY idx_payments_merchant_date ON payments(merchant_id, created_at DESC);
CREATE INDEX CONCURRENTLY idx_payments_failed ON payments(created_at DESC) WHERE status='failed';
-- CONCURRENTLY: builds indexes without locking the table