B+树
B+树是B树的一种变形
我们通过一颗四阶B+树来理解认识一下B+树:(如下:)
- 我们其实从图上就可以看出B+树和B树是有很多不同之处的
- 比如我们的B+树中将叶子结点层的所有结点使用一个链表串联了起来
- B+树中对于非叶子结点都是只是存储的索引(指针), 并没有存储关键字, 所以我们最终查询一个结果的时候要么是查询不到对应的关键字, 如果可以查询出结果, 那么我们的结果一定是在叶子结点中 —> 因为我们的B+树中将所有的关键字都存储到了叶子节点层中
- B+树中的外部结点不是虚设的, 我们的每个叶子结点(也就是关键字)都对应着一个外部结点, 在我们的MySQL中我们就是使用B+树作为底层结构维护的索引, 当我们查找到某个关键字的时候这个关键字就对应着数据仓库中的一条记录 , 但是我们的B树中也外部结点是虚设的, 指向B树中的外部结点的指针都是为空的, 因为我们的外部结点其实都是不存在的, 当我们使用B树查询的时候如果是查询到了外部结点的时候这个时候就说明没有对应的关键字, 也就表示查询不到
- 在B+树中一个n个关键字的结点会有n个子节点(也就是一个n结点有n个指针), 我们的每个关键字都对应着一个子节点, 我们的每个关键字都是对应的子节点中的最大的关键字值, 但是我们的B树中一个有n个关键字的结点会有n+1个子节点 —> 其实这个原因说白了其实是因为我们的B+树中非叶子结点是不存储关键字的(但是为什么是这样需要我们细细思考)
B+树的定义 : 一颗m阶B+树满足下列要求:
- 每个分支结点至多有m颗子树
- 根节点要么没有子树, 要么至少有两颗子树
- 除了根节点以外, 其他每个分支结点(非叶子结点)至少有Math.celi(m / 2)个子树, 每个分支结点至少有Math.celi(m / 2)个关键字
- 注意: 这里我们一定要注意我们B+树中的结点中的关键字的个数是和子节点的个数是相同的,并且都是Math.celi(m / 2)
- 所有叶子结点包含全部的关键字以及指向相应的记录的指针
- 而且叶子结点中是按照关键字大小顺序连接的, 并且所有的叶子结点是连接在一个单链表上的
- B+树中的外部结点是真实存储着数据的
- 所有分支结点(可以看做是索引的索引)中仅仅包含它的各个子节点(即下级索引的索引块)中最大关键字以及指向子节点的指针
- 我们的非叶子结点都是存储索引的, 所以指向非叶子结点的结点我们就可以称之为"索引的索引"
数据库中的索引就是通过B树和B+树来维护的
补充:
一定要知道我们的树的阶数是说的树中的拥有子节点最多的结点的子节点数目
- 我们一般将树中一个节点有多少个子节点称之为: “结点的度”
- 而我们的树的阶其实就是树的度, 就是指的树中所有结点中最大的度
