基于红黑树的本地缓存实现

[flycash]

在本地缓存实现里面，可以考虑使用不同的数据结构：

• 哈希结构，也就是目前用的最广泛的。但是哈希结构存在两个缺点：内存利用率不高，以及哈希扩容的时候，性能总是不平滑（虽然有些哈希实现会尽量实现平滑扩容）
• 跳表结构。缺陷就是极端情况下会退化为链表
• 树形结构：可以考虑的选择是红黑树、B 树，B+ 树。目前来看，在基于内存的实现里面，树的高度即便高一点性能也不会有很大损耗。

所以，可以提供一个基于红黑树的本地缓存实现。

该实现要求：

• 控制住内存使用量，直接控制缓存的键值对数量就可以
• 设计淘汰策略，直接提供 LRU 或者 LFU 中的一种就可以。这里我们的希望是能够有一个抽象的优先级的概念，每次淘汰都是淘汰优先级最低的那个，换句话来说，机制是按照优先级淘汰。LRU 和 LFU 只是一种比较特殊的计算优先级的策略。

在 ekit 里面已经有了红黑树的实现，你可以直接使用。但是 ekit 里面的红黑树没有直接暴露出来（目前在internal 包里面），所以你可以先在本地的时候修改 ekit 的代码，暴露出来，然后提交合并请求的时候，在两个项目里面都提交合并请求。

[flyhigher139]

跳表极端情况下退化为链表的概率很低吧？我前段时间在自己练手数据结构的库里实现了一份，明哥看看能用么？

考虑到正常情况下跳表的实现和易维护性比红黑树高很多，相应也更容易扩展，是不是实现一个基于跳表的本地缓存也有意义？

[flycash]

还是使用红黑树。虽然概率很低，但是如果你没有调整跳表的机制，那么还是不太合适。不是说不能用，而是说会出问题。大部分用户不具备排查跳表退化的性能问题。

[flyhigher139]

好的，这个issue这周没人认领的话，下周我接过来搞搞看。今年我工作有变动，很久没有写代码了，很久也没参与开源了 :P