闲聊Kvrocks中List结构

版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc

1. List 结构

List中的数据会被存储在2个列族中

1) list metadata

        +----------+------------+-----------+-----------+-----------+-----------+
key =>  |  flags   |  expire    |  version  |  size     |  head     |  tail     |
        | (1byte)  | (Ebyte)    |  (8byte)  | (Sbyte)   | (8byte)   | (8byte)   |
        +----------+------------+-----------+-----------+-----------+-----------+

2) list sub keys-values

                     +---------------+
key|version|index => |     value     |
                     +---------------+

head和tail的初始值是UINT64_MAX / 2

redis_metadata.cc

ListMetadata::ListMetadata(bool generate_version) : Metadata(kRedisList, generate_version) {
  head = UINT64_MAX / 2;
  tail = head;
}

2. 使用

2.1 使用 LPUSH

LPUSH mylist "A"

subKey的序列如下

mylist|1689243593|{UINT64_MAX/2}     =>  "A"

继续执行

LPUSH mylist "B"
LPUSH mylist "C"

subKey的序列如下

mylist|1689243593|{UINT64_MAX/2 - 2} =>  "C"
mylist|1689243593|{UINT64_MAX/2 - 1} =>  "B"
mylist|1689243593|{UINT64_MAX/2}     =>  "A"

2.2 使用 RPUSH

RPUSH mylist2 "A"

subKey的序列如下

mylist2|1689243587|(UINT64_MAX/2)

继续执行

RPUSH mylist2 "B"
RPUSH mylist2 "C"

subKey的序列如下

mylist2|1689243587|{UINT64_MAX/2}      =>  "A"
mylist2|1689243587|{UINT64_MAX/2 + 1}  =>  "B"
mylist2|1689243587|{UINT64_MAX/2 + 2}  =>  "C"

大家可以看出，LPUSH和RPUSH 得到的index编号都是连续的。
令萌叔感到好奇的是Kvrocks如何处理LINSERT。

2.3 使用 LINSERT

LINSERT可以在列表中的中间插入一个元素

假定初始时subKey的序列如下

mylist|1689243593|1     =>  "A"
mylist|1689243593|2     =>  "B"
mylist|1689243593|3     =>  "C"

执行LINSERT

LINSERT mylist AFTER "B" "newElement"

subKey的序列如下

mylist|1689243593|1     =>  "A"
mylist|1689243593|2     =>  "B"
mylist|1689243593|3     =>  "newElement"   // 需要执行put操作     
mylist|1689243593|4     =>  "C"           //  需要执行put操作     

在上面的例子中 mylist|1689243593|2 后面的键值对都需要执行put操作。因此时间复杂度是O(n)

因此官方文档也说了，当List中的元素过多时，不要使用这个命令。

参考资料

1.Kvrocks:data-structure-on-rocksdb
2.Kvrocks:Supported commands
3.Redis:LINSERT

---