红黑树和AVL树比较

插入：引起书的不平衡，AVL和红黑树最多两次自旋，时间复杂度都是O(logn)；

删除：AVL树往上回溯多个节点保持平衡，平衡时间复杂度是O(logn)，而红黑树最多只需要三次旋转时间，平衡时间复杂度是O(1)；

搜索：avl搜索稳定性要高于红黑树。

结论：如果删除和插入较多可以使用红黑树，否则使用avl树。

为什么zset使用跳表而不使用红黑树？

1、跳表是一个空间换时间的数据结构，跳表节点里面含有往上的指针，往下的指针，往前的指针，往后的指针。

2、跳表的数据结构相对于红黑树来说比较简单，这就是得，跳表在插入、删除的时候并不需要染色，自旋等复杂的操作。

redis是一个追求速度的单线程服务，所以选择跳表

B树

B+树

优点：

• 查询速度更稳定
• 树天然具备排序功能
• 全节点遍历更快