方法4：索引加速搜索

索引是用来加速查找的数据结构。不同的需求会使用不同的数据结构来构建索引。比如HashMap、Btree、SkipList都是经典的索引数据结构。

Redis

对于redis，数据在内存中。其key是一个字符串，使用哈希表可以直接映射，加速查找过程。

typedef struct redisDb {
    kvstore *keys;
} redisDb;

struct _kvstore {
    dict **dicts;
};

struct dict {
    dictEntry **ht_table[2];
};

另外在有序表的数据结构下，Redis使用到了跳表加速查找过程。

Mysql

Mysql提供多种数据结构作为索引。但是作为数据库，B+树基本是首选。

  enum enum_index_algorithm  // similar to ha_key_alg
  {
    IA_SE_SPECIFIC = 1,
    IA_BTREE,
    IA_RTREE,
    IA_HASH,
    IA_FULLTEXT
  };

Kafka
对于Kafka，每个日志段文件（.log）都配合又两个index文件：

1. 偏移量索引文件 (Offset Index File)：文件扩展名为 .index
2. 时间戳索引文件 (Timestamp Index File)：文件扩展名为 .timeindex

对于偏移量索引文件，可以快速定位给定目标消息偏移量在 .log 文件中的物理位置（字节偏移），它存储的条目是稀疏的。Kafka 不会为每条消息都创建索引项。默认每写入 4096 字节就生成一条索引条目，索引条目是按偏移量（绝对或相对）严格排序的，这使得可以在索引文件上使用高效的二分查找 (Binary Search)。

对于时间戳索引文件，可以快速定位给定时间戳之后的第一条消息的偏移量（主要用于按时间戳查找消息、处理 OffsetForTime 请求、日志保留策略等）。我们可以配合偏移量索引使用。它同样是稀疏索引，索引点通常与 .index 文件的索引点对齐（也受 log.index.interval.bytes 影响）。条目按时间戳严格排序（对于同一个日志段内的消息）。