B树、B+树速记
B树
- 每个节点最多有m-1个关键字(可以存有的键值对)。
- 根节点最少可以只有1个关键字。
- 非根节点至少有m/2个关键字。
- 每个节点中的关键字都按照从小到大的顺序排列,每个关键字的左子树中的所有关键字都小于它,而右子树中的所有关键字都大于它。
- 所有叶子节点都位于同一层,或者说根节点到每个叶子节点的长度都相同。
- 每个节点都存有索引和数据,也就是对应的key和value。
- 所以,根节点的关键字数量范围:1 <= k <= m-1,非根节点的关键字数量范围:m/2 <= k <= m-1
插入【B树、B+树速记】直接插入到叶节点的对应位置,如果数量超过m则分裂,将中间k上升到父结点中
B+树 B+树其实和B树是非常相似的,我们首先看看相同点。
相同点:
- 根节点至少一个元素
- 非根节点元素范围:m/2 <= k <= m-1
- B+树有两种类型的节点:内部结点(也称索引结点)和叶子结点。内部节点就是非叶子节点,内部节点不存储数据,只存储索引,数据都存储在叶子节点。
- 内部结点中的key都按照从小到大的顺序排列,对于内部结点中的一个key,左树中的所有key都小于它,右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
- 每个叶子结点都存有相邻叶子结点的指针,叶子结点本身依关键字的大小自小而大顺序链接。
- 父节点存有右孩子的第一个元素的索引。
- 单一节点存储的元素更多,使得查询的IO次数更少,所以也就使得它更适合做为数据库MySQL的底层数据结构了。
- 所有的查询都要查找到叶子节点,查询性能是稳定的,而B树,每个节点都可以查找到数据,所以不稳定。
- 所有的叶子节点形成了一个有序链表,更加便于查找。
推荐阅读
- activiti|springboot集成activiti5.6 ,接口报401、403
- 对象、数组、函数等多种数据类型的深浅克隆(拷贝)
- 微服务|RabbitMQ之消息可靠性、死信交换机、惰性队列及集群
- TASKCTL工程、流程、作业、参数节点数超界处理方法
- 2022钉钉发布会|云钉低代码新模式、新能力、新机遇
- 从零开始,开发一个|从零开始,开发一个 Web Office 套件(13)(删除、替换已选中文字)
- 『现学现忘』Docker基础|『现学现忘』Docker基础 — 33、Docker数据卷容器的说明与共享数据原理
- 数据库篇(mysql日志类型之|数据库篇:mysql日志类型之 redo、undo、binlog)
- python|【Rust日报】2022-03-22 fluent-uri(一个快速、简单和严格的URI解析器)
- SAP|SQLServer2005 百炼成钢