b树/b+树、时间轮、跳表、LSM-Tree-Toy模板网

这篇具有很好参考价值的文章主要介绍了b树/b+树、时间轮、跳表、LSM-Tree。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

b树、b+树：关系型数据库核心存储结构

1、为什么磁盘数据存储结构用B+树、而不用红黑树

b树/b+树、时间轮、跳表、LSM-Tree,b树,lsm-tree,数据结构

磁盘每次读取不是读一个节点、是返回一页数据。

红黑树每次遍历一个节点排除一半数据。

B树通常映射相邻的磁盘页数据。4K

mysql索引一个节点隐射16k故而映射4倍，故可以存储更多信息。

红黑树相对平衡，平衡黑节点故搜索时间复杂度不稳定。而B+树绝对平衡搜索稳定，数据都在叶子节点方便范围查询，遍历。

B+树高度更低，层次越到磁盘io次数就越多。如何降低：减少次数，化为顺序IO。

时间轮：海量定时任务检测

多线程环境下定时器设计

定时器：

1、以时间序来组织按照过期时间排序数据结构。

如使用：红黑树 nginx、workfllow

最小堆 libuv、go ：当前时间与最小过期节点比较

2、以执行序来组织

两个结构：

a、指针数组

b、时间指针

一个规则：

时间指针按照最小时间精度移动

1s size = 16 一秒移动一次，添加过期时间移动到哪，就把链表数据都取出来执行。

b树/b+树、时间轮、跳表、LSM-Tree,b树,lsm-tree,数据结构

由于时间精度和最大时间范围

多层级时间轮：支持更大时间范围

比如：钟表秒针精确存储，分针时针稀疏存储

每个小时，都会有时针层级的任务映射到分针层级...

b树/b+树、时间轮、跳表、LSM-Tree,b树,lsm-tree,数据结构

多线程加锁并发度

红黑树时间复杂度logN时间越长，等待时间越长。

1、时间轮O（1）时间短

2、加锁粒度

跳表:高并发有序存储 redis

概率型数据结构logN 二分查找每次比较排除一半节点

多层级有序链表

b树/b+树、时间轮、跳表、LSM-Tree,b树,lsm-tree,数据结构文章来源地址https://www.toymoban.com/news/detail-679285.html

到了这里，关于b树/b+树、时间轮、跳表、LSM-Tree的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

b树/b+树、时间轮、跳表、LSM-Tree