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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/**
 * Simple on-disk hash index implementation
 * Demonstrates the core concepts of hash-based file indexing
 */
 
#define BUCKET_COUNT 1024
#define ENTRIES_PER_BUCKET 16
 
typedef struct {
    char key[32];           // Search key
    off_t offset;           // File offset of data record
} HashEntry;
 
typedef struct {
    HashEntry entries[ENTRIES_PER_BUCKET];
    int count;
    off_t overflow_ptr;     // Pointer to overflow bucket (0 if none)
} HashBucket;
 
typedef struct {
    int index_fd;           // File descriptor for index file
    int data_fd;            // File descriptor for data file
    int bucket_count;
} HashIndex;
 
// Simple djb2 hash function
unsigned long hash_key(const char *key) {
    unsigned long hash = 5381;
    int c;
    while ((c = *key++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}
 
// Lookup: Find record offset by key
off_t hash_index_lookup(HashIndex *idx, const char *key) {
    // 1. Compute hash and determine bucket number
    unsigned long bucket_num = hash_key(key) % idx->bucket_count;
    
    // 2. Read the bucket from index file
    HashBucket bucket;
    off_t bucket_offset = bucket_num * sizeof(HashBucket);
    pread(idx->index_fd, &bucket, sizeof(bucket), bucket_offset);
    
    // 3. Search within the bucket
    for (int i = 0; i < bucket.count; i++) {
        if (strcmp(bucket.entries[i].key, key) == 0) {
            return bucket.entries[i].offset;  // Found!
        }
    }
    
    // 4. Check overflow bucket if exists
    if (bucket.overflow_ptr != 0) {
        // Recursively search overflow chain
        // (simplified: in production, iterate instead)
        return -1;  // Not found (simplified)
    }
    
    return -1;  // Key not found
}
 
// Insert: Add a key-offset pair to the index  
int hash_index_insert(HashIndex *idx, const char *key, off_t offset) {
    unsigned long bucket_num = hash_key(key) % idx->bucket_count;
    
    HashBucket bucket;
    off_t bucket_offset = bucket_num * sizeof(HashBucket);
    pread(idx->index_fd, &bucket, sizeof(bucket), bucket_offset);
    
    // Check if bucket has room
    if (bucket.count < ENTRIES_PER_BUCKET) {
        // Add entry to bucket
        strncpy(bucket.entries[bucket.count].key, key, 31);
        bucket.entries[bucket.count].offset = offset;
        bucket.count++;
        
        // Write bucket back
        pwrite(idx->index_fd, &bucket, sizeof(bucket), bucket_offset);
        return 0;
    }
    
    // Bucket full: would need overflow handling
    // (allocate overflow bucket, link from parent)
    return -1;  // Overflow not implemented in simplified example
}
 
/*
 * Performance characteristics:
 * 
 * - Lookup: O(1) average, O(n) worst case (all in one bucket)
 * - Insert: O(1) average, O(1) amortized with rehashing
 * - Range query: O(n) - must scan all buckets
 * - Space: O(n) entries + O(B) buckets overhead
 * 
 * Real implementations use:
 * - Extendible hashing (grows without full rehash)
 * - Linear hashing (incremental growth)
 * - Cuckoo hashing (guaranteed O(1) lookup)
 */

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 of order 4 (max 3 keys per node):
 
                        [30 | 60 |   ]  ← Root (internal)
                       /     |     \
                      /      |      \
         [10|20|  ]    [40|50|  ]    [70|80|90]  ← Internal nodes
          /  |  \       /  |  \       /  |  |  \
         ↓   ↓   ↓     ↓   ↓   ↓     ↓   ↓   ↓   ↓
        [L1][L2][L3]  [L4][L5][L6]  [L7][L8][L9][L10]  ← Leaf nodes
 
Leaf nodes contain:
- Actual key values
- Pointers to data records
- Link to next leaf (for range scans)
 
Example leaf node L4:
+-------------------------+
| 31 → offset 4500        |
| 35 → offset 2200        |
| 38 → offset 9100        |
| next_leaf → L5          |
+-------------------------+
 
To find key 35:
1. Start at root [30|60]
2. 35 > 30 and 35 < 60, go to middle child [40|50]
3. 35 < 40, go to leftmost child (L4)
4. Linear search in L4, find 35 → offset 2200
5. Seek to offset 2200 in data file
 
Total I/Os: 3 (root page + internal page + leaf page)
For 1 billion records, tree height ≈ 4 → only 4 I/Os per lookup!

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
41
42
43
44
45
46
47

LSM Tree Structure:
 
┌─────────────────────────────────────────────────┐
│                   MEMORY                         │
│  ┌─────────────────────────────────────────┐    │
│  │   Memtable (red-black tree or skiplist) │    │
│  │   Holds recent writes, sorted by key    │    │
│  │   Write: O(log n)  Read: O(log n)       │    │
│  └─────────────────────────────────────────┘    │
│           ↓ (when full, flush to L0)            │
├─────────────────────────────────────────────────┤
│                    DISK                          │
│                                                  │
│  Level 0: [SST1] [SST2] [SST3]                  │
│           (recently flushed, may overlap)        │
│                    ↓ (compact to L1)             │
│                                                  │
│  Level 1: [  SST-A  ] [  SST-B  ] [  SST-C  ]   │
│           (non-overlapping, 10x size of L0)      │
│                    ↓ (compact to L2)             │
│                                                  │
│  Level 2: [   SST-X   ] [   SST-Y   ] [   SST-Z   ]│
│           (10x size of L1)                       │
│                    ↓                             │
│  Level N: [...largest files...]                  │
└─────────────────────────────────────────────────┘
 
SSTable (Sorted String Table) format:
┌─────────────────────────────────────────────────┐
│  [Data Block 0] [Data Block 1] ... [Data Block N]│
│  [Index Block: key → block offset]               │
│  [Bloom Filter: fast negative lookups]           │
│  [Footer: metadata and offsets]                  │
└─────────────────────────────────────────────────┘
 
Read path for key K:
1. Check memtable (RAM) — O(log n)
2. Check bloom filters for each L0 SSTable
3. Binary search in L0 SSTables that might contain K
4. Check bloom filter for L1, binary search, etc.
5. Continue down levels until found or confirmed absent
 
Write path for key K:
1. Write to memtable — O(log n)
2. Done! (Flush and compaction are background)
 
This is why LSM is fast for writes!

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

/**
 * Secondary index example: Index users by email
 * Primary index: user_id → user record
 * Secondary index: email → user_id
 */
 
typedef struct {
    int user_id;
    char email[128];
    char name[64];
    // ... other fields
} User;
 
// Primary index: user_id → file offset (B-tree)
// secondary_email_idx: email → user_id (B-tree)
 
// Find user by email (using secondary index)
User* find_user_by_email(DB *db, const char *email) {
    // Step 1: Look up email in secondary index
    // Returns the user_id for this email
    int user_id = btree_lookup(db->email_index, email);
    if (user_id < 0) {
        return NULL;  // Email not found
    }
    
    // Step 2: Look up user_id in primary index
    // Returns the file offset for this user
    off_t offset = btree_lookup(db->primary_index, user_id);
    
    // Step 3: Read the actual record
    User *user = malloc(sizeof(User));
    pread(db->data_fd, user, sizeof(User), offset);
    
    return user;
}
 
// Insert new user (must update both indexes)
int insert_user(DB *db, User *user) {
    // 1. Write record to data file
    off_t offset = append_record(db->data_fd, user, sizeof(User));
    
    // 2. Add to primary index: user_id → offset
    btree_insert(db->primary_index, user->user_id, offset);
    
    // 3. Add to secondary index: email → user_id
    btree_insert(db->email_index, user->email, user->user_id);
    
    return 0;
}
 
// Find all users in a city (non-unique secondary index)
// city_index stores: city → list of user_ids
UserList* find_users_by_city(DB *db, const char *city) {
    // Get posting list: all user_ids in this city
    int *user_ids;
    int count = btree_get_posting_list(db->city_index, city, &user_ids);
    
    UserList *result = create_user_list(count);
    
    // Fetch each user via primary index
    for (int i = 0; i < count; i++) {
        off_t offset = btree_lookup(db->primary_index, user_ids[i]);
        User user;
        pread(db->data_fd, &user, sizeof(User), offset);
        add_to_list(result, &user);
    }
    
    free(user_ids);
    return result;
}

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
 
/**
 * Practical file index implementation
 * Uses a sorted index file with binary search
 * Suitable for read-heavy workloads with batch updates
 */
 
#define INDEX_ENTRY_SIZE 40
#define KEY_SIZE 32
 
typedef struct {
    char key[KEY_SIZE];
    off_t offset;
} IndexEntry;
 
typedef struct {
    int index_fd;           // Index file descriptor
    int data_fd;            // Data file descriptor  
    IndexEntry *cache;      // In-memory index cache
    int entry_count;        // Number of entries
    int cache_dirty;        // Needs write-back
} FileIndex;
 
// Load index into memory
FileIndex* index_open(const char *index_path, const char *data_path) {
    FileIndex *idx = calloc(1, sizeof(FileIndex));
    
    idx->index_fd = open(index_path, O_RDWR | O_CREAT, 0644);
    idx->data_fd = open(data_path, O_RDWR | O_CREAT, 0644);
    
    // Determine index size
    off_t size = lseek(idx->index_fd, 0, SEEK_END);
    idx->entry_count = size / sizeof(IndexEntry);
    
    // Load entire index into RAM
    if (idx->entry_count > 0) {
        idx->cache = malloc(idx->entry_count * sizeof(IndexEntry));
        pread(idx->index_fd, idx->cache, size, 0);
    }
    
    return idx;
}
 
// Binary search for key (O(log n))
off_t index_lookup(FileIndex *idx, const char *key) {
    if (idx->entry_count == 0) return -1;
    
    int left = 0, right = idx->entry_count - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = strcmp(idx->cache[mid].key, key);
        
        if (cmp == 0) {
            return idx->cache[mid].offset;  // Found
        } else if (cmp < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;  // Not found
}
 
// Range query: find all keys in [start_key, end_key]
int index_range_query(FileIndex *idx, 
                       const char *start_key, 
                       const char *end_key,
                       off_t *results, 
                       int max_results) {
    // Find starting position with binary search
    int left = 0, right = idx->entry_count - 1;
    int start_pos = idx->entry_count;  // Default: past end
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int cmp = strcmp(idx->cache[mid].key, start_key);
        
        if (cmp >= 0) {
            start_pos = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    // Scan forward collecting matching entries
    int count = 0;
    for (int i = start_pos; 
         i < idx->entry_count && count < max_results; 
         i++) {
        if (strcmp(idx->cache[i].key, end_key) > 0) {
            break;  // Past end of range
        }
        results[count++] = idx->cache[i].offset;
    }
    
    return count;
}
 
// Insert new entry (maintains sorted order)
int index_insert(FileIndex *idx, const char *key, off_t offset) {
    // Find insertion point
    int pos = 0;
    while (pos < idx->entry_count && 
           strcmp(idx->cache[pos].key, key) < 0) {
        pos++;
    }
    
    // Expand cache
    idx->cache = realloc(idx->cache, 
                         (idx->entry_count + 1) * sizeof(IndexEntry));
    
    // Shift entries to make room
    memmove(&idx->cache[pos + 1], 
            &idx->cache[pos],
            (idx->entry_count - pos) * sizeof(IndexEntry));
    
    // Insert new entry
    strncpy(idx->cache[pos].key, key, KEY_SIZE - 1);
    idx->cache[pos].offset = offset;
    idx->entry_count++;
    idx->cache_dirty = 1;
    
    return 0;
}
 
// Flush index to disk
void index_sync(FileIndex *idx) {
    if (!idx->cache_dirty) return;
    
    // Rewrite entire index file (simple but not optimal)
    ftruncate(idx->index_fd, 0);
    pwrite(idx->index_fd, idx->cache, 
           idx->entry_count * sizeof(IndexEntry), 0);
    fsync(idx->index_fd);
    idx->cache_dirty = 0;
}
 
// Close and cleanup
void index_close(FileIndex *idx) {
    index_sync(idx);
    close(idx->index_fd);
    close(idx->data_fd);
    free(idx->cache);
    free(idx);
}