一些前置概念
- n：单个节点内，元素的个数
- d：degree 树的度，即叶节点的元素数量。二叉树的度就是2，而B树的度便是叶节点的元素数量（可能，无确定数据源）。此外，B树的内节点内的元素存在上下界 d ≤ n ≤ 2d
- h：树高，也有称阶层，可以通过 log d ((N+1)/2) 计算出树高上上限（N为索引数量/树内所有元素的数量）
构成B-Tree的几个条件：
B-Tree
-
每个内节点（即非叶节点），都由 n-1 个元素（key）与 n 个指针构成。
n的取值范围：d ≤ n ≤ 2d
image.png
-
每个叶节点，至少包含 1 个元素，2 个指针
至多（2d-1）个元素，2d个指针
所有指针都指向null
3.所有叶节点深度相同，等同于树高
4.单一节点内，从左到右形成 非递减排列（即左 ≤ 右）
5.如果某一指针在节点最左，且不为null，则其指向的节点中的所有key，都小于该指针右侧的key
image.png
6.反之，最右侧的不为null的指针，指向的节点的key都大于指针左侧的key
image.png
B-Tree高效的原因
根据其特性，因此从根节点通过二分法进行查找，查找一个key时间复杂度为O(log d N )
image.png
但当插入、删除数据时会破坏B树的特性，需要额外的算法来维护
构成B+Tree的条件（树高至少2的情况）：
B+Tree
- 内节点不储存数据，只有叶节点储存
- 根节点至少有2个指针被使用（例如77的指针未指向任何节点）
- 除了根节点，其他节点至少包含(h/2)、至多包含h个元素，而指针最多也是h个
如上图，树高是3，至少非根节点至少包含1.5≈2个元素，至多包含3个元素 - 对于所有内节点，有多少元素就有多少指针
- 叶节点按照顺序排列
- 一般B+树都是带顺序访问指针，也即叶节点的尾指针会指向下一个节点的首元素
B树与B+树最大的区别便是只有叶节点能挂载数据（个人更直观的理解）
这也导致B+树的叶节点可以进行顺序访问，当读取一大片的数据时是非常有效率的（同时也可以利用物理硬盘对于顺序读取快的特性）
B+Tree（B-Tree）高效的原因
除了刚才分析的可以通过二分法快速找到索引外
B+树通过将单个节点存储在物理硬盘的单个块中
即只需单次IO读写便可以知道当前节点是否包含所要查找的元素
（因为物理硬盘数据读取的速度主要受限于IO读写的次数）
前面也提过，查找数据的时间复杂度O(h)也即O(log d N) ，而实际开发过程中树的度d会非常大（比如100），因此树高h会非常小
而h也正是实际查询的次数
这便是B+树高效的原因
而对比红黑树，他的h则会远远大于B+树，所以效率会大打折扣
MySQL中的B+Tree
1.5之前的mysql使用的是MyISAM，后来才改为InnoDB
MyISAM的特点有如下
image.png
- 叶节点挂载的是数据的地址，因此数据和索引是分离的（因此MyISAM也称非聚集索引）
- 辅助索引与主索引在数据结构上并没有太大区别（但辅助索引是可重复的）
InnoDB的特点
image.png
- 叶节点挂载的是数据，因此InnoDB本身就是主索引（比如可以通过查找15来找到DD）。因为这个特性InnoDB也被称为聚集索引
- 因为没有地址信息，InnoDB的辅助索引一般储存主索引（主键）
关于InnoDB的辅助索引的用途
如果需要查找一个名为FF的数据，则可以根据ASCII码来创建该字段的辅助索引（形成顺序排列）
然后获取到主键序号（FF→55）,再从主索引中获取FF相应的信息
（需要进行2次查找）
InnoDB总结
- InnoDB通过主索引（主键）来查找数据会比MyISAM更高效，因为InnoDB不需要再去查找主文件
- 主键不宜过长，辅助索引会引用主索引，所以过长的主索引会非常浪费空间
- 主键需要单调性（即主键适合使用1、2、3...而不是周、淑、怡...）
因为非单调的主键当遇到插入新的元素时会破坏B树的特性，从而需要更多的资源来维护他
因此，对于InnoDB而言，使用单调自增的字段作为主键是非常好的选择
参考链接
http://blog.codinglabs.org/articles/theory-of-mysql-index.html
把这篇文章的内容搜一搜，基本营销号一提到B树基本都是抄这的
由于我本身数据库非常厌恶（可能和教的人有关，之前js学的也很糟糕，直到看了石川的课）
到了索引使用策略及优化部分看不懂也看不进（可能没这么高的需求）
最后，作者也说了写一篇这样的博文需要半个月
我比较愚笨消化了快1天
但如果你只是点赞收藏，1秒都不要
而知识最终也不会进脑子
网友评论