B树和B+树
Mysql建立索引对于整个效率是很重要的，大大提交mysql检索速度。Mysql索引的数据结构大家都知道是B+树，那接下来首先介绍一下B树、B+树。
树这种数据结构（二叉树、红黑二叉树）都是为了解决系统查询慢的问题。二叉树特点，每个非叶子节点都只有两个孩子节点，当数据量特别大，会导致树的深度很大IO操作也增加，对整个查询并没有起到任何操作。
B树定义（平衡多叉树） 每个节点可以存储更多的值，降低IO操作
- 除了根节点每个节点至少有一个关键字
- 节点的值按照升序排序
- 每个节点对子树的范围有所分割。节点有个指针指向子树
- 所有子节点有相同的深度，即树的高度
B树结构.png
B+树定义 - 有k个子节点，必然有K个关键码
- 非叶节点进具有索引作用，记录信息值均放在叶节点中
- 树的所有叶节点构造是一个有序链表，按照次序查找能得到全部记录。
B+树结构.png
为什么Mysql选择B+树作为索引的数据结构？
1、B树多路存储，每次加载B树一个节点然后一步步往下找，每次载入一个节点到内存中
2、Mysql在查询的时候不止查找一条记录，为了防止B树在进行中序遍历，存在跨层访问。而B+树通过非叶子节点找到数据起始位置后，按照它的非叶子节点是一个有序链表的结构，能够迅速查找到其他的值。B+树循序数据分批次加载，同时树的高度提高了查询效率。当B+树的高度达到4层，其实已经可以存储上千万的数据了。
索引分类
- 主键索引：为主键创建的索引每个表有且只有一个，如果创建表的时候没有指定Mysql则会选择一个唯一性的字段默认设置为主键索引。Mysql在查询的时候直接搜索主键树就可以返回。
- 普通索引：可以创建多个普通索引，但是在Mysql查询的过程中，首先通过普通字段查询普通索引树查询到主键，然后再根据主键搜索主键索引树查找到这条记录。这一个过程称为回表操作。
- 唯一索引：不允许字段有重复。比如身份证号码等信息。
- 全文索引：用于文章的检索。可以在char、varchar、text等类型字段创建。
注意：
为了性能和存储空间考虑，我们最好保证主键越小越好。因为普通索引树存储着主键值。这样不仅保证主键树的大小而且保证普通索引的大小。
B+树占用磁盘空间，如果整个树很大数据页满了B+树会申请新的数据页，挪动一部分数据过去这个过程称为页分裂,当数据删除的时候也会存在页合并过程。整个性能也降低，
综上所述从性能和存储空间考虑自增主键更加合理。
覆盖索引：
执行一条查询语句，查询的结果正好在普通索引树上，可以直接提供查询结果不需要进行回表。覆盖索引可以减少树的搜索次数，显著提升查询性能，是常用的优化手段。
最左前缀原则：
B+树这种索引结构，利用索引的"最左前缀"来定位记录，索引项按照索引定义里出现字段顺序排序的。当建立联合索引的时候，我们就得考虑索引的复用能力。当索引为（a,b）如果查询条件只有b字段，则不走索引。
网友评论