# 索引


## ***索引的基本种类***

1. ***Innodb***
   - *`主键索引`在建立主键的时候就会自动帮你创建一个主键索引，在Innodb引擎下主键索引是聚簇索引，可以不唯一*
   - *`普通索引`除主键外，任意一列创建的索引就叫做普通索引 普通索引可以有多个*
   - *`唯一索引`跟主键索引唯一的区别就是 该索引是唯一的，可以为null*
   - *`联合索引`一个索引包含多个列*
2. **MyISAM**
   - *`全文索引`全文索引类型为 FULLTEXT, 在定义索引的列上支持值的全文查找, 允许在这些索引列中插入重复值和空值 可以在 char varchar text类型列上创建*

## ***索引的优点缺点***

1. ***优点***
   - *能够大大加快索引的查询速度*
2. **缺点**
   - *索引会占用磁盘空间*
   - *维护索引需要消耗数据库的资源*
   - *在 insert update delete操作下 会性能下降 因为要维护索引*

## ***最左匹配原则***

1. ***现在有一个联合索引包含了 name age bir 三个列***
   - *name bir age 能否利用索引 - yes*
   - *name age bir 能否利用索引 - yes*
   - *age bir 能否利用索引 - no*
   - *bir age name 能否利用索引 - yes*
   - *age bir 能否利用索引 - no*
2. ***面对上述问题 有两个要注意***
   - *最左匹配原则 也就是 "name" or "name age" or "name age bir" 就可以走索引*
   - *mysql 引擎在查询为了更好利用索引 在查询过程中会动态优化查询字段*
3. ***a = 1 and b = 1 and c > 1 and d = 1***
   - ***联合索引 走到范围查询就会停止 所以这里d不会走到索引***

## ***索引的妙用***

1. ***SELECT***
   - *如果有这样的char列，前10个字符都是唯一的，可以建立短索引（前缀索引）这样能加快查询效率 并且减少磁盘io*
2. ***WHERE***
   - *`!=` `not in`这些并不会使用索引，但是`<` `>`等 都可以使用索引*
   - *如果where子句使用到函数 则不会走索引*
   - *如果where子句已经使用过索引 orderby 并不会使用索引 所以真要使用orderby 最好建立联合索引*
   - *如果用 `like` `%like%` `%like` 不使用索引 `like%` 才会使用*
   - *如果用 `or`如果 `or` 前后的两个条件的列都是索引, 那么查询会使用索引， 如果前后两个条件有一个不是索引 则不会使用索引*
3. ***JOIN***
   - *在需要join的列最好用索引 但是要注意 主键与外键的类型必须是相同的 要不然不走索引*
4. ***使用索引建议性原则***
   - *在 查询中很少使用 或者参考的列不要创建索引。由于这些列很少使用到，增加索引反而会降低系统的维护速度和增大空间需求*
   - *只有很少数据值的列 也不应该增加索引，由于这些列的取值很少，区分度太低。例如人事表中的性别,在查询时,需要在表中搜索的数据行的比例很大, 增加索引，并不能明显加快检索速度*
   - *定义为 text、image 和 bit 数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少*
   - *当 修改性能远远大于检索性能 时，不应该创建索引。这是因为，二者是相互矛盾的，当增加索引时，会提高检索性能，但是会降低修改性能*
   - *定义有 外键 的数据列一定要创建索引*

## ***B+ Tree***

1. ***B+ Tree导出过程***
   
   - *举个例子 现在有几条数据 在底层存储是这么存储的绿色: 主键 / 红色: 数据 / 蓝色: 指针 下一个数据(node)*
     
     ![b+树 - 链表形态](https://raw.githubusercontent.com/vlicecream/cloudImage/main/data/202301311330164.png)
   
   - *但是这样随后问题就来了 数据量少就算了 如果有1000条数据 链表时间复杂度为O(n) 所以mysql采用了 **分页（升维）**的思路每一个数据都会存放着自己的那一页的第一条数据的逐渐 随后指针p指向自己的分页的下一级数据*
     
     ![b+tree 升维后的跳表](https://raw.githubusercontent.com/vlicecream/cloudImage/main/data/202303021739126.png)
   
   - *然后我们把第一层的页目录再次提取一层，最终用了三层的结构*
     
     ![b+树 终极形态](/Users/ting/Library/Application Support/typora-user-images/image-20230302174409156.png)

2. ***b+ tree总结***
   
   - *B+树本质上是一种多叉平衡二叉树，是由多个页组成的多层级结构，每个页16Kb，对于主键索引来说，最末级的叶子结点放行数据，非叶子结点放的则是索引信息(主键id和页号)，用于加速查询*
   - *B+树利用了空间换时间、升维的方式(构造了一批非叶子结点用于存放索引信息)，将查询时间复杂度从O(n)优化为O(lg(n))*

## ***B+ Tree 和 跳表的区别***

1. ***查询***
   - *B+树是多叉树结构，每个结点都是一个16k的数据页，能存放较多索引信息，所以扇出很高。三层左右就可以存储2kw左右的数据 / 跳表是链表结构，一条数据一个结点，如果最底层要存放2kw数据，且每次查询都要能达到二分查找的效果，2kw大概在2的24次方左右，所以，跳表大概高度在24层左右，所以得出结论 **b+Tree的查询效率要比跳表高得多***
2. ***写***
   - *B+树需要拆分合并索引数据页，跳表则独立插入，并根据随机函数确定层数，没有旋转和维持平衡的开销，因此跳表的写入性能会比B+树要好*
3. *其实，mysql的存储引擎是可以换的，以前是myisam，后来才有的innodb，它们底层索引用的都是B+树。也就是说，你完全可以造一个索引为跳表的存储引擎装到mysql里。事实上，facebook造了个rocksDB的存储引擎，里面就用了跳表。直接说结论，它的写入性能确实是比innodb要好，但读性能确实比innodb要差不少*
4. ***redis为什么使用跳表而不使用B+树或二叉树呢?***
   - *大家知道，redis 是纯纯的内存数据库。进行读写数据都是操作内存，跟磁盘没啥关系，因此也不存在磁盘IO了，所以层高就不再是跳表的劣势了。并且前面也提到B+树是有一系列合并拆分操作的，换成红黑树或者其他AVL树的话也是各种旋转，目的也是为了保持树的平衡。而跳表插入数据时，只需要随机一下，就知道自己要不要往上加索引，根本不用考虑前后结点的感受，也就少了旋转平衡的开销。因此，redis选了跳表，而不是B+树*
5. ***总结***
   - *B+树是多叉平衡搜索树，扇出高，只需要3层左右就能存放2kw左右的数据，同样情况下跳表则需要24层左右，假设层高对应磁盘IO，那么B+树的读性能会比跳表要好，因此mysql选了B+树做索引*
   - *redis的读写全在内存里进行操作，不涉及磁盘IO，同时跳表实现简单，相比B+树、AVL树、少了旋转树结构的开销，因此redis使用跳表来实现ZSET，而不是树结构*
   - *存储引擎RocksDB内部使用了跳表，对比使用B+树的innodb，虽然写性能更好，但读性能属实差了些。在读多写少的场景下，B+树依旧YYDS*

## ***B Tree 与 B+ Tree的区别***

1. *B Tree  非叶子结点也会存储数据 这样会导致 树的高度比 b+ tree 高 查询磁盘io次数也会比 b+ tree高  这样会影响查询效率*
2. *B+ Tree    只有叶子节点会存储数据 非叶子节点只存储键值信息 注意 不是键值对哦~    所有叶子节点之间都有一个键指针*

## ***聚簇索引 & 非聚簇索引***

1. ***聚簇索引***
   - *将数据与索引存放在一块 索引结构的叶子节点保存了行数据*
2. ***非聚簇索引***
   - *将数据与索引分开存储 索引结构的叶子节点指向了数据对应的位置(注意 不是地址哦~)*
3. ***注意事项***
   - *在Innodb中, 在聚簇索引之上创建的索引称之为辅助索引. 非聚簇索引都是辅助索引*
   - *像联合索引 唯一索引 前缀索引叶子节点存储的不再是行的物理位置，而是主键值*
   - *辅助索引访问数据总是二次查找*

## ***在不同引擎下的索引***

1. ***Innodb***
   - *Innodb使用的是聚簇索引，将主键组织到一颗b+树中，而行数据就储存到叶子节点*
   - ***使用 `WHERE id = 14`这样的主键条件的查询过程***
     - *按照 b+ tree 的检索算法即可找到对应的叶节点，之后获得行数据*
   - ***使用 非主键 `WHERE name = 'Ame'` 的条件查询过程***
     - *在辅助索引b+ tree中检索name，到达其叶子节点获取对应的主键*
     - *使用主键在主索引b+ tree中在执行一次b+ tree检索操作，最终到达叶子节点即可获取整行数据*
   - *聚簇索引默认是主键，如果表中没有定义主键，Innodb会选择一个唯一且非空的索引代替，如果还是没有这样的索引，Innodb会隐式定义一个主键来作为聚簇索引*
   - *如果已经设置了主键为聚簇索引又希望再单独设置聚簇索引，必须先删除主键，然后添加我们想要的聚簇索引，最后恢复设置主键即可*
2. ***MyISAM***
   - *MYISAM使用的是非聚簇索引 非聚簇索引的两颗b+树看上去没什么不同 节点的结构一样 只是存储的内容不同    主键索引b+树的节点存储了主键, 辅助索引b+树存储了辅助键 这两颗b+树的叶子节点都使用一个地址指向真正的表数*

## ***使用聚簇索引的优势***

1. ***引出***
   - *每次使用辅助索引都要经过两次 b+树查找, 看上去聚簇索引的效率明显要低于非聚簇索引, 所以使用聚簇索引优势在哪*
2. *由于行数据和聚簇索引的叶子节点存储在一起, 同一页会有多条数据, 访问同一数据页不同行记录时, 已经将页加载到了buffer*
3. *辅助索引的叶子节点, 存储主键值, 而不是数据的存放地址. 好处是当行数据发生变化时, 索引树的节点也需要变化    或者是我们需要查找的数据, 在上一次io读写的缓存中没有, 需要发生一次新的io操作时, 可以比避免对辅助索引的维护工作， 只需要维护聚簇索引树就好了    还有一个因为辅助索引存放的主键值 还少了辅助索引占用的存储空间大小*

## ***mysql的主键类型***

1. ***mysql不推荐uuid为主键***
   - *uuid不适合排序且可能会出现新增加记录的uuid 会插入在索引树中间的位置 导致索引树调整复杂度变大 消耗更多的时间和资源*
   - *建议使用int bigint类型, 方便排序并且默认会在索引树的末尾增加主键值*

## ***参考资料***

- *《MYSQL内核：INNODB存储引擎 卷1》*
- *《RocksDB和Innodb引擎性能PK胜负难料?》*
- *https://cloud.tencent.com/developer/article/1813695*
- *https://www.51cto.com/article/706701.html*