索引的作用是让健值数据库根据Key找到对应Value的存储位置，进而进行操作。

实现

索引的类型有很多，常见的有哈希表、B+树、字典树等。为了实现从健到值的快速访问，Redis使用了一个全局哈希表来保存所有的健值对。

之所以采用哈希表作为索引，很大的一部分原因在于，其健值数据基本都是保存在内存中的，而内存的高性能随机访问特性可以很好地与哈希表O(1)的操作复杂度相匹配。

哈希表本身就是一个数组，数组中的每个元素都是一个哈希桶，每个哈希桶中都保存着健值对数据。

  • 健：存储指向Key所在内存地址的指针
  • 值：存储指向Value所在内存地址的指针

image.png

哈希冲突

既然使用来哈希表，难免会照成哈希冲突。所谓的哈希冲突是指两个Key的哈希值相同从而导致两个数据落到了同一个哈希桶中。

Redis通过链式哈希去解决哈希冲突。链式哈希是指同一个哈希桶中的多个元素用一个链表存储，链表中的数据用指针依次连接。
image.png

rehash

随着哈希表中的数据越来越多，哈希冲突也会随之增多，由于冲突链上的数据只能逐一查找，进而导致元素查找耗时长、效率低下。为了解决这个问题，Redis会对哈希表做rehash操作。

rehash操作是通过增加现有哈希桶数量，让逐渐增多的数据能在更多的哈希桶间分散保存，从而减少单个哈希桶中的元素个数。

Redis默认使用了两张全局哈希表，一开始有数据进来时默认使用哈希表1，此时并没有为哈希表2分配空间，随着数据逐步增多，Redis开始执行rehash操作：
image.png
由于Redis是单线程的，为了避免在拷贝数据时造成线程阻塞无法处理其它请求，Redis使用了渐进式的rehash：
image.png
以上，就是Redis索引的实现。