type
status
date
slug
summary
tags
category
icon
password
这里写文章的前言：
一个简单的开头,简述这篇文章讨论的问题、目标、人物、背景是什么？并简述你给出的答案。
可以说说你的故事：阻碍、努力、结果成果，意外与转折。
📝 数据结构
跳表
定义
特点
思想
空间换时间，时间复杂度，O(logn)
B树
定义
特点
思想
空间换时间，对于IO次数减少作用
B+树
定义
特点
思想
空间换时间，对于IO次数减少作用，相比B树范围查询更好，查询复杂度更稳定
红黑树
定义
特点
不能范围查询
思想
时间换空间，解决快速查找元素的问题，时间复杂度是O(logn)
时间轮
定义
特点
思想
空间换时间，解决根据任务的轻重缓急分片(环形数组)执行任务，提高并发度的问题。它的加锁方式是对整个时间轮进行加锁，但是时间轮的处理速度是O(1)的时间复杂度来分配任务和修改任务。这样就使得加锁的时间很短来提高并发
LSM（log structured merge）树
定义
特点
思想
空间换时间，读多写少
👨🏻💻B树和B+树的区别
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定。
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字和数据，所以在查询这种数据检索的时候会要比B+树快。
👨🏻💻红黑树和B树的区别
- 策略不一样，红黑树属于内排序，b树属于外排序，它们复杂度相同或者相近的排序方法虽然有很多种，但是这些排序方法依然是不同的排序算法；
- 红黑树是二叉树的变种， b树一个节点代表数据的集合或者范围；
- 从应用层面看，红黑树适合小数据范围内的快速查找，然而b树适合大范围数据查找。
并发度提高的方式
- 降低锁的粒度；
- 降低锁的持有时长；
📎 参考文章
有关中间件数据结构的问题，欢迎您在底部评论区留言，一起交流~
- 作者:Sheamus
- 链接:https://www.sheamus.top/article/middleware/datastruct
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
