1.B-Tree的原理分析
（1）什么是B-Tree
- B-树，全称是 Balanced Tree，是一种多路平衡查找树。
- 一个节点包括多个key (数量看业务)，具有M阶的B树，每个节点最多有M-1个Key。
- 节点的key元素个数就是指这个节点能够存储几个数据。
- 每个节点最多有m个子节点，最少有M/2个子节点，其中M>2。
- 数据集合分布在整个树里面，叶子节点和非叶子节点都存储数据；类似在整个树里面做一次二分查找。
- B 树相对于平衡二叉树，每个节点存储了更多的键值（key）和数据（data）。
- 实际业务中B树的阶数一般大于100，存储大量数据，B树高度也会很低，查询效率会更高。
- 备注
- 每个节点拥有最多的子节点，子节点的个数一般称为阶。
- 阶：m阶是代表每个节点最多有m个分支（子树）。
- 树的度：这棵树里面节点最大的度。
- 节点的度：当前节点有几个子节点。
（2）B树插入原理
- 每个节点的数据都是顺序存储，具有M阶的B树，树的阶数表示每个结点最多可以有多少个子结点
（3）B树的应用场景
- 在数据库中，B树用来维护索引，用来提高查询效率，一个节点可以存储整个页（即磁盘块）
- 在文件系统中，B树用来存储文件的目录信息，提高文件的访问效率
- 在操作系统中，B树可以用来存储内存管理信息，提高内存的分配效率
- （4）思考：3层的B树，阶数为1024，最多容纳多少个元素？
- B树的阶数表示每个结点最多可以有多少个子结点，因此B树的阶数为1024，表示每个结点最多可以有1024个子结点
- 由于B树的3层，因此根结点可以有1024个子结点，每个子结点又可以有1024个子结点
因此一个3层的B树，阶数为1024，B树的每一层的节点数都是阶数的幂次方
计算总容量 把每一层的节点数相加 即10241+10242+1024^3 大约是 11亿个节点，假如每个节点放一个元素就是11亿个
所以在10亿个数据中找目标值，常规小于3次磁盘IO即可找到目标值，比平衡二叉树的30次提升了不少
- 平衡二叉树的高度就等于每次查询数据时磁盘 IO 操作的次数。
- 10亿的数据量，log2(N)约等于30次磁盘IO，
- log2(N) 相当于2的多少次方（立方）等于N，例：log2 (8）= 3
- 2的30次方=1073741824，所以就是30次磁盘IO
2.B+Tree的原理分析
（1）什么是B+Tree
- 是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，同等存储空间下比B-Tree存储更多key
- 非叶子节点不对关键字记录的指针进行保存，只进行数据索引 , 树的层级会更少 , 所有叶子节点都在同一层,
- 叶子节点的关键字从小到大有序排列，叶子节点之间用指针连接, 构成有序链表（稠密索引）
- B+树上每个非叶子节点之间是一个双向链表进行链接，而叶子节点中的数据都是使用单向链表链接
查找特点
- 当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找
- 继续沿着关键字的指针向下，每次查询必须到叶子节点才能真正获取到相关数据
- B+Tree叶子节点相连接，对树的遍历就是只需要 一次线性遍历叶子节点
- 由于叶子节点的数据是顺序排列，方便区间查找
- 在B+树完成范围查找，排序查找，分组查找，去重查找 比B树效率也比较高
（2）B+Tree插入流程解析
总结
- B树和B+树的最大区别在于非叶子节点是否存储数据
- B+树非叶子节点只是当索引使用，同等空间下B+树存储更多key
- B树,非叶子节点和叶子节点都会存储数据，找到对应节点就有对应的数据
- B+树, 只有叶子节点才会存储数据,存储的数据都是在一行上，找到非叶子节点的key，还需要继续找到叶子节点才可以获取数据
- B树的节点包括了key-value，所以找到对应的key即可找到对应的value，不用在继续寻找
- 两种树各有优缺点和应用场景
3.B+Tree树应用之Mysql索引底层原理剖析
- 背景
- Mysql数据库是大家用最多的，查询是最高频使用的操作
- 在多数数据库的设计里面，会用B-Tree或B+Tree做索引提高查询效率
- 基于一张数据库的表数据进行查询（类似mysql的user表）
- 构建索引：id用做key，然后data是数据的存储地址
| 内存地址 | id | phone | name | Age |
| 0xFS | 843 | 13820835467 | 张三 | 43 |
| 0xER | 984 | 15738235423 | 李四 | 20 |
| 0x32 | 4212 | 12152354223 | 王五 | 18 |
| 0x93 | 1000 | 12152356324 | 赵六 | 30 |
| 0xAP | 2341 | 18735622097 | 李祥 | 19 |
| 0xSQ | … 1千万条数据 | … | … | … |
精确查找 id=2341的数据 select * from user where id = 2341
- 未使用索引
- 自上而下查找数据，一行行遍历，5次才找到数据
- 使用索引
- id建立主键索引（B+Tree结构），对应的数据存储数据的地址，2次找到数据，且数据量越多效果越明显
- 根节点是常驻内存的，不需要进行IO操作
- 范围查找 id>1000 和 id < 4212 的用户
- 未使用索引
- 自上而下查找数据，一行行遍历
- 使用索引
- id建立主键索引（B+Tree结构），由于本身是有序链表，所以顺序查找即可
- Mysql的InnoDB中的索引结构与MyISAM的索引结构的区别
- InnoDB引擎,表数据文件按B+Tree组织的，叶节点data域保存完整行数据, 树上的key就是主键, 以主键构建的B+树索引
- 这种索引叫做聚集索引（聚簇索引 clustered index）
- 聚簇索引一般为主键索引，而主键一个表中只能有一个，所以聚集索引一个表只能有一个
- 聚簇索引叶子节点存储的是行数据，而非聚簇索引叶子节点存储的是聚簇索引（通常是主键 ID）
- MyISAM引擎：索引文件和数据文件是分开的，索引结构的叶子节点放的是指向数据的主键（或者是地址）构建的B+树索引
这种索引叫做非聚集索引、二级索引、辅助索引（非聚簇索引 nonclustered index）
非聚集索引一个表可以存在多个
叶子节点中保存的不是实际数据，而是主键，获得主键值后去聚簇索引中获得数据行
注意
非聚簇索引的叶子节点上存储的并不是真正的行数据，而是主键 ID或记录的地址
当使用非聚簇索引进行查询时，会得到一个主键 ID，再使用主键 ID 去聚簇索引上找真正的行数据，把这个过程称之为回表查询
所以聚簇索引查询效率更高，而非聚簇索引需要进行回表查询，性能不如聚簇索引
非聚簇索引的叶子节点上存储的并不是真正的行数据，而是主键 ID或记录的地址
当使用非聚簇索引进行查询时，会得到一个主键 ID，再使用主键 ID 去聚簇索引上找真正的行数据，把这个过程称之为回表查询
所以聚簇索引查询效率更高，而非聚簇索引需要进行回表查询，性能不如聚簇索引
