文章目录
- 为啥不用二叉搜索树？
- 为啥不用平衡二叉（avl）树？
- 为啥不用b-树？
- 为啥用b+树？（重点）
- 索引
- 聚簇索引
- 聚簇索引的局限
- 聚集的数据的优点
- 非聚簇索引介绍
- 组合索引
- 覆盖索引
- 前缀索引
- 前缀索引选择算法
- 全文索引
- hash索引
- b-tree索引
- 自适应哈希索引
- 小咸鱼的技术窝
b-tree索引使用的是b+树的数据结构，树有这么多种，那为啥就选择b+树呢？那就从为啥使用b+树开始，到分析其原理的思路一步步分析吧。以下内容针对innodb来说
为啥不用二叉搜索树？
二叉搜索树定义：
- 非空左子树的所有键值小于其根结点的键值。
- 非空右子树的所有键值大于其根结点的键值。
- 左、右子树都是二叉搜索树。就是左节点<根节点<右节点。 看下图树太高了。查询效率太低，故不推荐。
为啥不用平衡二叉（avl）树？
平衡二叉（avl）树定义：
- 非叶子节点最多拥有两个子节点。
- 非叶子节值大于左边子节点、小于右边子节点。
- 树的左右两边的层级数相差不会大于1。
- 没有值相等重复的节点。
虽然avl树对于二叉树来说是平衡了降低了树的高度，虽然提高了性能，但是数据量大一点的时候，高度依旧很高。毕竟定义一摆在那，非叶子节点怎么找最多也只能有俩个子节点，故不推荐。
为啥不用b-树？
b-树定义：
- 在一个节点中，存放着数据（包括key和data）以及指针，且相互间隔。
- 同一个节点，key增序。
- 一个节点最左边的指针不为空，则它指定的节点左右的key小于最左边的key。右边同理。中间的指针指向的节点的key位于相邻两个key的中间。
- B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。
- 每个非叶子节点由n-1个key和n个指针组成，其中d<=n<=2d。
简单点来说呢，b-树又称多路查找树相对于avl树来说就是每个节点下面可以有多个分叉。至少多于2个叉撒，对于百万级别的数据又是降低了树的高度，虽然提高了性能，但是由于每个索引节点都有存放
data域的指针，而我们计算机每次从磁盘读取数据时以页（4kb）为单位，每次读取4096byte的数据，导致读取单个节点时，可能由于节点过大，每次读出的数据有限，从而增大io次数，故在mysql这种关系型数据库中不推荐。但是b-树还是有它自己的优点的，如果查找的节点，离根节点很近那么查找的效率还是很高的
为啥用b+树？（重点）
b+树定义：
- 内节点不存储data，只存储key和指针；叶子节点不存储指针，存key和data。
- 内节点和叶子节点大小不同。
- 每个节点的指针上限为2d而不是2d+1
b+树相对与b-树来说好的地方就是：
- 数据只在叶子节点上面才有。解决了b-树非叶子节点过大导致io次数过多的问题。
- 树高更低同时由于非叶子节点不放数据，单个节点能存的关键字更多了，极大的降低了树的层级高度。
- 可以范围查找由于叶子节点之间是有一个有序链表来维护的，进行范围查找十分方便，单向的还是双向的不清楚，先搁着下面测试在来看。
- 全节点遍历更快b+树只需扫描叶子节点，而不是像b-树那样逐层扫描每个节点
- 查询速度更稳定如果是b-树，查离根节点近的速度就快，远的就慢，而b+树数据全在叶子节点，每次查找的速度都相同
到此为啥使用b+树就有底了。那么开始正文。。。。。
索引
索引定义：一种数据结构
按照范围从大到小来说吧，最大的是聚簇索引、非聚簇索引。接着是我们常说的b-tree索引、hash索引，而我们的覆盖索引、前缀索引、组合索引、复合索引、全文索引是基于b-tree、hash索引来说的，还有的就是Innodb引擎独有的自适应哈希索引下面一一展开了来说。
聚簇索引
聚簇索引定义：是一种存储数据的方式，数据与索引在一个文件中。它的辅助索引的叶子节点存储的是指向行的指针。
一般来说innodb是按照主键来进行聚集的，这就意味着被索引的列就是主键列。如果主键不存在，其次就是按照非空唯一性约束来进行聚集，如果这个约束都没得，其次就是按照Innodb它自己生成的一个隐藏主键列来聚集。那么使用聚簇索引有什么优缺点吗？当然是有的。
聚簇索引的局限
如果我们往聚簇索引中插入非顺序的数据时的情况下面
- 由于新行的主键不一定比前一个大，Innodb不能总是把数据插入到最后一行，因此需要为新行进行寻找位置，从而进行多次随机的io
- 更新数据时innodb有时不得不进行分页，为新行开辟内存空间，这会导致移动大量的数据
- 页面会因为分页变得稀疏不规则从而就会导致一些不规则的碎片产生
- 在没有覆盖索引的情况下，查辅助索引的时候，经常需要回表
而且如果我们按照主键顺序插入行的情况下，使用uuid來聚集也是不好的。也会产生写，到磁盘上的数据被重新读取出来，并且由于位置的不确定，也会导致大量的数据移动
聚集的数据的优点
- 聚集索引把数据和索引全部放到一个b-tree下面，从聚集索引中取得数据通常比非聚集索引取得的数据更快，因为不需要二次查找。
- 对于范围查询的效率很高，因为数据是有序的
非聚簇索引介绍
非聚簇索引是什么呢？其实我们所说的辅助索引、第二索引啊啥的其实可以理解为就是非聚簇索引。非聚簇索引就是叶子节点的data域中存的不是完整的数据，而是指向磁盘数据的指针。
组合索引
定义：单列索引的组合。我感觉和覆盖索引没啥差别，假设现在有一张表（test）有a,b,c,d,e这么几个字段，其中我们为a，b，c列添加一个索引叫a_b_c，这个就是组合索引。
覆盖索引
定义：索引列已经包含了我们需要查询的数据。其实就是组合索引（复合索引）在特定情况下的又一别称。假设现在有一张表（test）有a,b,c,d,e这么几个字段，其中我们为a，b，c列添加一个索引叫a_b_c，现在select a,b,c from test where a = x1 and b = x2 and c = x3;我们需要查询的数据在辅助索引上面已经有了，此时使用的就是复合索引。
前缀索引
定义：为数据的前面几个字段创建的索引。我个人理解其实就是单列索引的变种。那为什么要为前几个字符创建索引而不是为其全部来创建索引呢？原因也是很简单，这个得结合应用场景来说了。现在有这么一张表，专门是存储家庭地址的，一个地址动不动就是十来个字的长度，如果我们以全部长度来创建索引，那么这个索引文件是超级的大啊。此时创建前缀索引是个不错的选择，可以大幅度压缩索引的大小，那么我们该如何确定前缀索引的长度的呢？这就是涉及到一个算法了。
前缀索引选择算法
不重复的索引值/所有行 = 比值，这个比值接近7的时候，所得到的结果就会越加精确。
全文索引
参考
hash索引
使用的场景：一些读操作密集的表建议使用hash索引，因为hash索引的查找速度是很快的。但是也有一些局限。
hash索引的局限性：
- hash索引只包含哈希码和行指针，不能使用索引的值避免读取行，也就是要回表，不能像覆盖索引那样避免回表。
- hash索引不能进行排序以及范围查找，因为它们不会按照顺序保存行。
- 有可能产生hash碰撞，那么就必须要访问链表的每一个行指针，然后逐行进行比较得出正确数据。
- 只支持 = 、in 、<=>的比较，为啥呢原因很简单，不会按照顺序存行。
- 不支持部分键匹配，例如有个组合索引a_b，那么此时即使我们的where子句中使用到了a，也不会使用索引。
b-tree索引
底层数据结构b+tree，对比hash的局限来看，hash索引的局限在b-tree索引这都不是事，除了hash索引查询速度快这点上面
自适应哈希索引
与其说这是一种索引不如称其为是一种机制。自适应哈希索引的由来就是：当Innodb注意到一些索引值被频繁的访问时，内部会在b-tree索引的顶端为其创建索引保存在内存之中，使其具有快速哈希查找的特性，这个过程是它自动完成的
小咸鱼的技术窝
关注不迷路，日后分享更多技术干货，B站、微信公众号同名，名称都是（小咸鱼的技术窝）更多详情在主页