1. B树和B+树
0. 基本概念
- 度：节点的子节点数量
- 阶：一个节点的子节点的最大数量（M阶代表一个树节点最多有多少个子节点）
1. B树 == B- 树
一种平衡多叉查找树。可以是空树，或一个M阶数满足以下性质：
- 根结点至少有两个子节点
- 排序方式：所有节点关键字是按递增次序排列
- 子节点数：非叶节点的子节点数>1，且<=M ，且M>=2
- 关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个；ceil()——向上取整
- 除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加1
- 所有叶子节点均在同一层
B树的节点插入规则：
- 节点拆分：当前是要组成一个M阶查找树，关键字数必须<=M-1，关键字数>M-1 就要进行节点拆分
- 排序规则：比左大，比右小
B树的节点删除规则：
- 节点合并：当前是要组成一个M阶查找树，关键字数必须大于等于ceil（M/2）-1，否则就要进行节点合并
- 排序规则：比左大，比右小
- 关键字数小于ceil（M/2）-1时先从子节点取，子节点没有符合条件时就向向父节点取
优势：
每个节点包含的关键字增多了，利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K），减少了与磁盘的I/O次数
2. B+树
B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。
M阶的B+树定义如下：
- 每个结点至多有m个子节点
- 根结点至少有两个子节点
- 除根结点外，每个节点至少有ceil(M/2)个子节点，最多M个子节点
- 有k个子节点的结点必有k个关键字
- 子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针
优势：
- B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快
- B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定
- B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高
- B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描
2. MyISAM
使用B+Tree作为索引结构
非聚集索引——索引和数据文件是分离的，索引保存的是数据文件的指针。主键索引和辅助索引是独立的
Myisam：frm是表定义文件，myd是数据文件，myi是索引文件
3. InnoDB
使用B+Tree作为索引结构
聚集索引——数据文件是和（主键）索引绑在一起的（表数据文件本身就是按B+Tree组织的一个索引结构），必须要有主键，通过主键索引效率很高。但是辅助索引需要两次查询，先查询到主键，然后再通过主键查询到数据。因此，主键不应该过大，因为主键太大，其他索引也都会很大。
推荐使用自增（整型）主键——增加插入操作的效率；
自增ID可以保证每次插入时B+索引是从右边扩展的，可以避免B+树和频繁合并和分裂（对比使用UUID）。如果使用字符串主键和随机主键，会使得数据随机插入，效率比较差
InnoDB：frm是表定义文件，ibd是数据文件
InnoDB引擎的4大特性:
- 插入缓冲/insert buffer
- 二次写/double write
- 自适应哈希索引/ahi
- 预读/read ahead
4. 比 较
- InnoDB支持事务，MyISAM不支持，对于InnoDB每一条SQL语言都默认封装成事务，自动提交，这样会影响速度，所以最好把多条SQL语言放在begin和commit之间，组成一个
- InnoDB支持外键，而MyISAM不支持。对一个包含外键的InnoDB表转为MYISAM会失败
- InnoDB是聚集索引；MyISAM是非聚集索引
- InnoDB支持表、行级锁(默认)，而MyISAM支持表级锁。InnoDB的行锁是实现在索引上的，而不是锁在物理行记录上。潜台词是，如果访问没有命中索引，也无法使用行锁，将要退化为表锁。
- InnoDB表必须有主键（用户没有指定的话会自己找或生产一个主键），而Myisam可以没有
- Innodb存储文件有frm、ibd，而Myisam是frm、MYD、MYI
来源点这里
5. 选 择
- 是否要支持事务，如果要请选择innodb，如果不需要可以考虑MyISAM
- 如果表中绝大多数都只是读查询，可以考虑MyISAM，如果既有读也有写，请使用InnoDB
- 系统奔溃后，MyISAM恢复起来更困难
Comments | NOTHING