088. 使用C语言实现简单的数据库索引

在C语言中实现一个简单的数据库索引，可以通过构建一个简单的哈希表或二叉搜索树来实现。这里以哈希表为例，展示一个简单的索引实现。哈希表可以快速定位数据，适合用于简单的键值对索引。

示例代码：简单的哈希表索引

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

#define TABLE_SIZE 100 // 哈希表的大小

// 定义哈希表节点结构
typedef struct Node {
    int key; // 键
    char value[100]; // 值（假设值为字符串）
    struct Node* next; // 指向下一个节点（用于处理哈希冲突）
} Node;

// 哈希表数组
Node* hashTable[TABLE_SIZE];

// 哈希函数
unsigned int hashFunction(int key) {
    return key % TABLE_SIZE;
}

// 初始化哈希表
void initHashTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }
}

// 插入键值对到哈希表
void insert(int key, const char* value) {
    unsigned int index = hashFunction(key);
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    strcpy(newNode->value, value);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// 查询键对应的值
char* search(int key) {
    unsigned int index = hashFunction(key);
    Node* current = hashTable[index];
    while (current != NULL) {
        if (current->key == key) {
            return current->value;
        }
        current = current->next;
    }
    return NULL; // 未找到
}

// 删除键值对
void delete(int key) {
    unsigned int index = hashFunction(key);
    Node* current = hashTable[index];
    Node* prev = NULL;
    while (current != NULL) {
        if (current->key == key) {
            if (prev == NULL) {
                hashTable[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

// 清理哈希表
void freeHashTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node* current = hashTable[i];
        while (current != NULL) {
            Node* temp = current;
            current = current->next;
            free(temp);
        }
    }
}

int main() {
    initHashTable();

    insert(1, "Alice");
    insert(2, "Bob");
    insert(3, "Charlie");

    printf("Search for key 1: %s\n", search(1)); // 输出 Alice
    printf("Search for key 2: %s\n", search(2)); // 输出 Bob
    printf("Search for key 3: %s\n", search(3)); // 输出 Charlie

    delete(2);
    printf("Search for key 2 after deletion: %s\n", search(2)); // 输出 NULL

    freeHashTable();
    return 0;
}

代码说明

哈希表结构：

• 使用一个固定大小的数组 hashTable 来存储哈希表的节点。

• 每个节点是一个链表，用于处理哈希冲突（链地址法）。

哈希函数：

• 使用简单的模运算 key % TABLE_SIZE 作为哈希函数。

插入操作：

• 计算哈希值，找到对应的数组位置。

• 将新节点插入到链表头部。

查询操作：

• 计算哈希值，遍历链表查找键。

• 如果找到，返回对应的值；否则返回 NULL。

删除操作：

• 计算哈希值，找到对应的链表。

• 遍历链表找到目标节点并删除。

清理操作：

• 遍历哈希表，释放所有动态分配的内存。

扩展

• 如果需要支持更大的数据量，可以动态调整哈希表的大小。

• 可以使用更复杂的哈希函数来减少冲突。

• 可以支持更多的数据类型作为键和值。

这个简单的哈希表索引实现可以作为数据库索引的基础，适用于一些小型或嵌入式系统中的数据管理。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)