【二】B+树

前言

B+树挺重要的，数据库索引就是用的B+树。

思考

为什么数据库索引不使用hash表或者其他数据结构。

定义

B+树，之前我们学习的搜索二叉树，和B+树类似，但是是多叉，且非叶节点不保存数据，只保存索引值，既然和搜索二叉树类似，就意味着B+树是有顺序的，这个特性很重要，顺序就意味能二分查找，形象的解释B+树就是多叉搜索树但非叶子没有值。

特性

• M必须大于2。
• 任何一个节点最多只有M-1个节点。
• 非叶节点不保存值。
• 叶子节点保存值。
• 所有叶子节点的高度一样。
• 每层的权值都是小到大的。

例图

M=3

image.png

每一层都是从小到大的，树的查找则是从顶层查找到叶子节点，查找的节点树就是树的高度，因为是多路，所以意味着树的高随着M的变大而变小。

Select/Insert/Delete

• Select：这个就是B+树的优势，为啥？因为树的高度低，查找的节点低，但是这个优势发挥的地方在磁盘存储，这个我们下面再说。
• Insert：插入树就涉及到节点的分裂，因为节点最多只能包含M-1个儿子，当叶子节点儿子数为M-1时插入新儿子就意味叶子的分裂，产生一个新的叶子节点，M个儿子就要分裂到旧和新两个叶子节点中，然后还要推选出一个父权值，且父权值的左右指针就是旧和新叶子，这个父权值要插入到旧叶子的父节点的儿子中去，这样又涉及到分裂问题，而且这个问题会循环到顶层非叶节点，而影响树根可能指向新的非叶节点。
• Delete：删除树的叶子节点儿子，比较简单，这个再详述。

个人总结

• 树的高度低。
• 非叶节点只存储索引值，叶子节点存储索引值和数据。
• 每一层都是有顺序的。

索引数据

数据库，意味着数据量会很大表的数据十几G上百G不稀奇，就MySQL来说InnoDB来说表的数据存储就是一个巨大的B+树，意味着一个B+树就是特别大，无法加载的内存中的，所以是存在磁盘中的。

• 索引很大，是存储在磁盘中的
• 磁盘是按叶存储的，假设一个叶的大小是1K，哪怕文件只有1个byte也要占用一个叶，计算机一次读取一叶效率是很低的，一般16个叶为一个桶，一次读取一个桶，提高读取效率，

来分析一下，要快速查找数据，数据在磁盘中，磁盘读取的效率比内存读取差几百倍，那优先问题，如何减少磁盘读取。

下面是几种数据结构的使用分析：

• 使用红黑树（本质还是搜索二叉树）意味着树的高度会很高，且叶和非叶都存储数据，意味着逻辑上市相连的，但是物理上可能很远，这样磁盘要频繁的转动，效率差。
• 使用hash树，没有顺序，无法顺序查找，需求不符合
• 使用B+树，假设索引的是int,4个字段,16K全部沾满的情况下可以存储65536个值，假设树的高度为3层，全部沾满的情况下可以存储655366553665536，大约是281474976710656个值，当然这个理论情况下，叶节点还保持的数据，这意味着叶子节点的儿子数量是少于65536的，但是还是能说明问题，一是树的高度低 读取磁盘的次数就低，且都是有顺序的查询性能是lgN，很高效，且支持顺序查找。

InnoDB

InnoDB的表数据结构就是一个以主键为权值的B+树 存储在磁盘中。

优化建议：

• 主键要尽可能的小,为啥？占用空间越小意味着一个桶能存储更多主键啊,这样意味树的高度可能会更低，需要读取的磁盘次数越少。
• 主键最好是单步递增,小表无所谓，大表就不一样了,非递增的主键插入就意味着没有顺序，而InnoDB是以顺序的为基本的，这样插入就是随机的，节点就会出现频繁的分裂或者很多节点存储的不满，空间占用高，查询效率低，但是主键单步递增就顺序插入，之前写满的节点不会再发生大的变动，空间使用率很高，查询效率也高。
• 副索引是建立在主索引之上的，副索引的叶子节点存储的是主键值，通过主键值再查询真实数据，主键不能过大，会拉低一切索引的效率。
• 表的值也不要存储过大，叶子节存储的是主键和数据，数据过大必然造成一个桶存储的儿子减少，影响查找效率。
• 一切都是B+树，更新数据必然造成B+树的删除的插入，都是成本，合理使用索引，索引不能过多。