ღゝ◡╹)ノ❤️

集中一点,登峰造极!

  menu
137 文章
0 浏览
0 当前访客
ღゝ◡╹)ノ❤️

数据结构

红黑树和AVL树比较

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

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

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

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

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

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

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

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

B树

B+树

优点:

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

标题:数据结构
作者:哇哇哇哇
地址:https://wuxiangshi.vip/articles/2022/04/08/1649378764249.html