[{"createTime":1735734952000,"id":1,"img":"hwy_ms_500_252.jpeg","link":"https://activity.huaweicloud.com/cps.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=V1g3MDY4NTY=&utm_medium=cps&utm_campaign=201905","name":"华为云秒杀","status":9,"txt":"华为云38元秒杀","type":1,"updateTime":1735747411000,"userId":3},{"createTime":1736173885000,"id":2,"img":"txy_480_300.png","link":"https://cloud.tencent.com/act/cps/redirect?redirect=1077&cps_key=edb15096bfff75effaaa8c8bb66138bd&from=console","name":"腾讯云秒杀","status":9,"txt":"腾讯云限量秒杀","type":1,"updateTime":1736173885000,"userId":3},{"createTime":1736177492000,"id":3,"img":"aly_251_140.png","link":"https://www.aliyun.com/minisite/goods?userCode=pwp8kmv3","memo":"","name":"阿里云","status":9,"txt":"阿里云2折起","type":1,"updateTime":1736177492000,"userId":3},{"createTime":1735660800000,"id":4,"img":"vultr_560_300.png","link":"https://www.vultr.com/?ref=9603742-8H","name":"Vultr","status":9,"txt":"Vultr送$100","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":5,"img":"jdy_663_320.jpg","link":"https://3.cn/2ay1-e5t","name":"京东云","status":9,"txt":"京东云特惠专区","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":6,"img":"new_ads.png","link":"https://www.iodraw.com/ads","name":"发布广告","status":9,"txt":"发布广告","type":1,"updateTime":1735660800000,"userId":3},{"createTime":1735660800000,"id":7,"img":"yun_910_50.png","link":"https://activity.huaweicloud.com/discount_area_v5/index.html?fromacct=261f35b6-af54-4511-a2ca-910fa15905d1&utm_source=aXhpYW95YW5nOA===&utm_medium=cps&utm_campaign=201905","name":"底部","status":9,"txt":"高性能云服务器2折起","type":2,"updateTime":1735660800000,"userId":3}]
一、红黑树
红黑树,用两种颜色标记节点;
* 所有节点只有红黑两种颜色
* 根节点永远是黑色的
* 每个叶子节点(null或NIL空节点)是黑色的
* 从一个节点到其所有子孙节点的路径上都包含一样多的黑色节点 (可确保)
* 红色节点的孩子是黑色
首先将红黑树当成一颗二叉查找树,把节点插入,然后对该节点进行着红色操作。着红色时一定不会违反红黑树上述的第四个特性。最后经过旋转和着色操作完善红黑树。
得益红黑树的五个特性,构建红黑树时的旋转操作更加简单。
二、B树
二叉树每个根节点只有两个子树,在数据量很大的时候,树的深度会很大。B树的存在解决了这个问题。
B树的节点包含键和值,是key-value的形式。一个节点可以包含多个key,并不确定,需要看具体实现。现在我们选择一个参数M来构建一个B树,我们可以将其称为M阶的B树。
* 每个节点最多有M-1个key,并且以升序排列
* 每个节点最多有M个子节点
* 根节点至少有两个子节点
B树的构建是自下而上的,当M-1个key被占满,就会有值被挤上去。
三、B+树
B+树和B树相似,不同的地方是只有叶子节点存储形式为key-value,其他节点存储的只有key值。树的所有叶节点构成一个有序链表,可以按照key排序的次序依次遍历全部数据。
B+ 树的优点在于:
1.B+树在非叶子结点上不包含数据的值,只当做索引使用,因此在内存相同的情况下,能够存放更多的key。
2.B+树的叶子结点都是相连的,因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。像有索引的链表。
B树的优点在于:
只需要找到key所在的位置,就能找到value,不用像B+树要一直找到叶子结点才能找到value。