跳跃表
redis中的sorted-set正是一种基于此原理的数据结构,可是为啥不用二叉树呢?它们之间的区别在哪里?
二叉查找树需要维持平衡,一般不用AVL,维护的代价比收益会大,只对查找有要求的情况下AVL优于红黑树.而一般使用红黑树的应用场景非常多.redis之所以不用,是因为redis是内存数据库,其设计理念就是要节省内存,跳表虽然空间复杂度是On但是可以通过调参来降低内存消耗.而且在并发环境下,跳表需要更新的部分比较少,需要加锁的地方也比较少,所以不同线程竞争锁的代价就少了.性能也就会比红黑树高了.