【二】B+树

2019-10-10 本文已影响0人 Michael_abc

前言

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

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

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

M=3

image.png

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

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的表数据结构就是一个以主键为权值的B+树存储在磁盘中。

优化建议：

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