45、数据库文件操作：基于标准库实现简单的键值存储（B-tree/哈希表）

说实话，很多C语言初学者都会问我一个问题：「没有MySQL，没有Redis，我能不能用C标准库自己搞一个数据库？」

我的回答是：当然可以。而且我建议你试试。

我自己在早年做嵌入式项目时，就遇到过这样的场景——设备上根本没有数据库服务，但数据又需要持久化存储。那时候我硬着头皮用标准库写了一个简单的键值存储。虽然简陋，但够用。今天我就把这里面的门道跟你聊聊。

45.1 键值存储的核心思路

说白了，键值存储就是一张大表。你给我一个Key，我返回一个Value。就这么简单。

但难点在于：数据要存到磁盘上，而且读写要快。

我常用的两种底层数据结构是：

  • 哈希表（Hash Table）：适合点查询，O(1) 的平均复杂度。但不支持范围查询。
  • B-tree：适合范围查询，O(log n) 的复杂度。但实现起来更复杂。

你想想看，如果你的应用只需要根据ID查用户信息，哈希表就够了。但如果你需要查「所有年龄在20到30岁之间的用户」，那就得上B-tree。

我的建议： 初学者先从哈希表入手。B-tree的节点分裂和合并操作，说实话挺绕的。我当年第一次写B-tree时，调试了整整两天。

45.2 基于哈希表的键值存储实现

我们先来看一个最简单的实现。用C标准库的 fopen、fwrite、fread 来操作文件。

核心思路是这样的：

  1. 把文件分成固定大小的「桶」（Bucket）。
  2. 每个桶里可以存多个键值对。
  3. 通过哈希函数计算Key应该落在哪个桶。
  4. 读写时直接定位到桶的位置。

嗯，这里要注意：桶的大小要提前定好。我一般用4KB，正好是一个磁盘块的大小，读写效率最高。

#include <stdio.h>
#include <string.h>
#include <stdint.h>

#define BUCKET_SIZE 4096
#define MAX_KEY_LEN 64
#define MAX_VAL_LEN 256
#define BUCKET_COUNT 1024

// 一个键值对
typedef struct {
    char key[MAX_KEY_LEN];
    char value[MAX_VAL_LEN];
    uint8_t valid;  // 1表示有效，0表示已删除
} KV_Pair;

// 一个桶：包含多个键值对
typedef struct {
    KV_Pair pairs[BUCKET_SIZE / sizeof(KV_Pair)];
    uint16_t count;
} Bucket;

// 哈希函数：简单的BKDR哈希
uint32_t hash(const char* str) {
    uint32_t hash = 0;
    while (*str) {
        hash = hash * 131 + (*str++);
    }
    return hash % BUCKET_COUNT;
}

// 写入键值对
int kv_put(const char* filename, const char* key, const char* value) {
    FILE* fp = fopen(filename, "rb+");
    if (!fp) return -1;

    uint32_t idx = hash(key);
    Bucket bucket;

    // 定位到对应的桶
    fseek(fp, idx * BUCKET_SIZE, SEEK_SET);
    fread(&bucket, sizeof(Bucket), 1, fp);

    // 查找空位或相同key
    for (int i = 0; i < bucket.count; i++) {
        if (strcmp(bucket.pairs[i].key, key) == 0) {
            // 更新已有key
            strncpy(bucket.pairs[i].value, value, MAX_VAL_LEN);
            fseek(fp, idx * BUCKET_SIZE, SEEK_SET);
            fwrite(&bucket, sizeof(Bucket), 1, fp);
            fclose(fp);
            return 0;
        }
    }

    // 新增键值对
    if (bucket.count < sizeof(bucket.pairs) / sizeof(KV_Pair)) {
        strncpy(bucket.pairs[bucket.count].key, key, MAX_KEY_LEN);
        strncpy(bucket.pairs[bucket.count].value, value, MAX_VAL_LEN);
        bucket.pairs[bucket.count].valid = 1;
        bucket.count++;

        fseek(fp, idx * BUCKET_SIZE, SEEK_SET);
        fwrite(&bucket, sizeof(Bucket), 1, fp);
        fclose(fp);
        return 0;
    }

    fclose(fp);
    return -2;  // 桶满了
}

// 读取键值对
char* kv_get(const char* filename, const char* key, char* out) {
    FILE* fp = fopen(filename, "rb");
    if (!fp) return NULL;

    uint32_t idx = hash(key);
    Bucket bucket;

    fseek(fp, idx * BUCKET_SIZE, SEEK_SET);
    fread(&bucket, sizeof(Bucket), 1, fp);
    fclose(fp);

    for (int i = 0; i < bucket.count; i++) {
        if (bucket.pairs[i].valid && strcmp(bucket.pairs[i].key, key) == 0) {
            strncpy(out, bucket.pairs[i].value, MAX_VAL_LEN);
            return out;
        }
    }

    return NULL;
}
小技巧： 我习惯把文件头预留一部分空间，用来存元数据，比如桶的总数、每个桶的大小。这样以后扩容时方便。

45.3 哈希表的问题与改进

上面这个实现有个明显的缺陷：哈希冲突。如果多个Key算到同一个桶，桶满了就写不进去了。

我在项目中遇到过这种情况：某个桶里塞了太多数据，导致后续写入全部失败。排查了半天才发现是哈希函数分布不均匀。

解决办法有几种：

  • 链地址法：每个桶里存一个链表指针，溢出数据链到下一个桶。但文件操作里实现链表比较麻烦。
  • 开放地址法：桶满了就往后找下一个空桶。简单，但容易导致数据聚集。
  • 多级哈希：用多个哈希函数，一个满了换另一个。我比较推荐这个。

我个人习惯用「线性探测再哈希」：

// 线性探测：如果目标桶满了，往后找
uint32_t find_slot(const char* filename, const char* key) {
    uint32_t idx = hash(key);
    uint32_t original = idx;

    do {
        // 检查这个桶是否可用
        // ... 读取桶数据，判断是否有空位或相同key
        idx = (idx + 1) % BUCKET_COUNT;
    } while (idx != original);

    return -1;  // 全满了
}
注意： 线性探测会导致「聚集效应」——冲突的Key会挤在一起，后续查询越来越慢。我曾经在一个生产环境里遇到过，查询延迟从1ms飙升到200ms。后来改用「二次探测」才解决。

45.4 B-tree 的简单实现思路

如果你需要范围查询，哈希表就无能为力了。这时候得上B-tree。

B-tree的核心思想是：每个节点存多个Key，节点之间有指针。这样一次磁盘IO可以读取多个Key，效率很高。

我画了一张图，帮你理解B-tree的结构：

根节点 [30, 60] 子节点 [10, 20] 子节点 [40, 50] 子节点 [70, 80] 叶子 [5, 8] 叶子 [15, 18] 叶子 [35, 38] 叶子 [45, 48] 叶子 [65, 68] 图例： 内部节点 叶子节点（存实际数据）

B-tree的代码实现比哈希表复杂得多。我这里只给你一个核心的节点结构定义：

#define ORDER 4  // B-tree的阶

typedef struct {
    int keys[ORDER - 1];          // 关键字数组
    long child_offsets[ORDER];    // 子节点在文件中的偏移量
    int key_count;                // 当前关键字数量
    int is_leaf;                  // 是否为叶子节点
    long data_offset;             // 叶子节点中数据的文件偏移量
} BTreeNode;

写B-tree时，最头疼的是节点分裂。当一个节点满了，要把中间的关键字提上去，左右分成两个节点。我当年第一次写的时候，指针指来指去，把自己都绕晕了。

我的经验： 写B-tree之前，先在纸上画几轮插入和删除操作。把每个步骤的节点状态画清楚，再动手写代码。这样能省掉至少一半的调试时间。

45.5 文件操作的性能优化

不管是哈希表还是B-tree，最终都要落到文件IO上。而文件IO是性能瓶颈。

我常用的优化手段：

优化手段 说明 效果
缓冲区缓存 在内存中缓存最近访问的桶/节点 减少磁盘IO次数
批量写入 攒够一批数据再写，而不是每次写一条 提升写入吞吐量
内存映射 用 mmap 代替 fread/fwrite 省去用户态和内核态的数据拷贝
预读 读取一个节点时，把相邻节点也读进来 减少随机IO

嗯，这里要特别说一下内存映射。用 mmap 之后，你可以像操作内存数组一样操作文件，代码会简洁很多。但要注意：mmap 在32位系统上有地址空间限制，文件太大可能映射不了。

// 使用 mmap 读取文件
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

void* map_file(const char* filename, size_t* size) {
    int fd = open(filename, O_RDWR);
    if (fd == -1) return NULL;

    struct stat st;
    fstat(fd, &st);
    *size = st.st_size;

    void* map = mmap(NULL, *size, PROT_READ | PROT_WRITE,
                     MAP_SHARED, fd, 0);
    close(fd);

    if (map == MAP_FAILED) return NULL;
    return map;
}
注意： 用 mmap 时，如果文件被其他进程截断或扩展，映射区域可能会失效。我在一个多进程项目中就踩过这个坑——一个进程写数据导致文件变大，另一个进程的映射区域直接段错误了。

45.6 总结与避坑指南

好了，说了这么多，我帮你理一下重点：

  • 哈希表：实现简单，适合点查询。注意哈希冲突和桶大小。
  • B-tree：支持范围查询，但实现复杂。节点分裂是难点。
  • 文件IO：用 mmap 提升性能，但要注意多进程安全问题。
  • 数据一致性：写入时最好先写临时文件，再 rename 覆盖原文件。防止写入中途崩溃导致数据损坏。

我曾经犯过一个低级错误：在写入键值对时，先写了数据，再更新索引。结果程序在中间崩溃了，索引和数据对不上，整个数据库废了。后来我改成「先写日志，再写数据，最后写索引」的顺序，才彻底解决这个问题。

如果你只是做个玩具项目，哈希表就够了。但如果你想搞个正经的嵌入式数据库，我建议你研究一下B-tree。虽然难，但值得。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →