mysql索引

阶数为1024，子树最多有1024个，子树的子树也是1024个，元素个数：1024+1024^2+1024^3≈11亿，

一般小于3次磁盘io可找到目标，平衡二叉树则要30次！

为啥是30次，10亿数据=log2(N)N等于30

这里在事物篇章点了下，在这里精讲
要熟悉B+树索引，页结构式必不可少的知识
因为通过页结构抛出问题，可以得到B+树的由来
页结构我们关注两点就可以了
1User Records
2Page Direct
上面这张图，下面的长方形是B+树的一个叶子，对应一个innoDB页，对应4个操作系统页
这个页存放了行记录，假设一个记录1kb，那么一页就可以对应16行数据，
	假设16个数据，等值查询第八个，假设没有页结构，
		流程这样的，加载1数据到内存，和8比，不是，再加载2数据，比较，
		会发生8次io，但是页结构，一次加载一页到内存，那么一次io就可以了。
		同理，存数据也是
那么B+树叶子结点对应一个页，他们直接有指针，那页里的行记录呢？
没错，也是链表，逻辑连续，但是物理空间是通过指针连起来的链表，且是有序的，
所以每次插入都要排序。且时间是不有好的，因为链表要遍历！
所以就可以解释：
	为何插入时推荐按自增id插入，如果 4231这样插，会把链表断开，时间就浪费了
		如果1234这样，直接插到后面就可以了
		而且，假如页满了，不按顺序的话，也会把这个页的一条记录提出来，性能就浪费了
			比如  1235一个页  插入4，   就会把5从页里取出，把4放进去
mysql如何解决链表结构查询慢的问题的？
	页目录，就是分类， 
		比如 1  2    4  5  6
	   页目录*1      *4
	   这里分两类，两个*是俩目录
	   
	  	假如，没有页目录，查询3，得全遍历一遍才知道没有3
	  	但是有的话，就从页目录知道，肯定不会在4以后，从1开始找，找俩，都不是3，就知道这个表里没3了！
	  好，那么页目录提高页内查询效率，那么多个页呢，100w数据，那么多叶子结点，我只查询第100w个数据，还得是从第一个遍历，
      同理，也是加目录，就引入了B+树

B+树叶子结点是有双向指针连接的，通过索引定位到地方后，
然后通过叶子结点的联系做到范围查询

刚刚，在分析索引页结构的时候，提到自增id可以适应B+树维护的有序链表，
但是不一定符合任何情况！
这两个各有优缺点：
自增主键id很明显，就是可充分利用B+树叶子维护的有序链表，插入，查询的效率都很高。
还有就是相较于uuid省空间。
自增的id还可以来解决深度分页问题
缺点就是安全了
首先分库分表就不能保证唯一了
然后id是自增的 可能会遭别有用心的竞争者分析数据量什么的，
	比如xx公司即将上市，号称用户量xxW，然后被竞争者通过数据库发现实际不足这么多数据量，泄露，股市崩盘，致命打击！！
		所以安全是必要的
uuid优点是唯一，不可预测，安全性强！！
作为主键最致命的就是不能使用叶子结点提供的有序链表，不能做范围查询，
其次是空间很大，以及仅仅是个唯一标识。没有参考意义。

那么有没有两者优点都有，然后还摒弃缺点的方案呢？
雪花算法：
首先他唯一且有意义,还有递增
既符合分布式下方案，又递增可以适配叶子结点构建的有序链表

这里我想从查询效率和查询稳定两方面来说
查询效率这里
首先innoDB一定会存在聚簇索引，
只在叶子结点存数据，而不存放指针，那么一个页就可以的大小会更多些，内存与磁盘的次数会少些
	同时叶子结点只存放数据，可以使页的大小固定，适合预读、并且大小固定，叶子分裂和并的时候io会减少
	非叶子结点只存索引，那么一个结点存的数据也就越多，提高缓存命中率
	还有一点就是叶子结点构成了一个有序链表，支持范围查询和排序，同时也方便预读。
上面说的是效率，
另外B+树查询稳定，因为走索引的话，查询的路径是一样长去命中叶子结点的数据，所以会稳定些 

为何不用二叉查找树？
二叉查找树会发生退还，发生倾斜，退化成线性表这样，另外二叉查找树在和B+树一样的数据量下，
行高是一个致命的打击。而B+树是一种磁盘io友好型数据结构，刚才说的叶子结点设计，有序链表的构建都减少io
为什么不使用红黑树？
红黑树来说他虽然不太可能发生退化成线性结构，但是他的路数树比较少的，深度就会比较大，另外它本身也不是很平衡

那你说说为啥不用B树?/B+树和B树的区别
最大区别就是B树非叶子结点也会存放数据，这样的话页存放的数据会少一些，磁盘交互更多，
同样的数据，高度会高，查询的链路会更长，效率会慢些
稳定性来说：每个结点都存放数据，查询就不会很稳定，有可能在第一次就能查到，有的就要找最底下才行

B+树是磁盘io友好数据结构  跳表是内存友好数据结构
跳表：可以理解为给链表+索引，每一层都是一个索引层
B+树和跳表都是为了达到二分查找的效果。
B+树和跳表对比：
	B+树优点3行数据可存储2200w数据，而对于跳表达到二分logN则需要24行，
	缺点是要耗费时间去维护B+树特性。而跳表动态性是很强的，特别是对于插入删除这样很适合Redis
	总结：B+树：优点3层存储2200w数据，缺点是需要维护B+树
		跳表：优点：低成本的支持动态的插入删除，缺点是行高很大。
	然后回答的适合可通过行高和是否需要维护这两方面去说！
首先innoDB三行B+树可以存放2200w数据，
而这些数据用跳表存储的话，
跳表想要达到二分查找的效果，log2(N=22002，也就是2的24次方，需要经过24次磁盘io，
这对于mysql磁盘存储来说，效率是很低的
而对于Redis来说，Redis是基于内存的，层高不会造成io问题
其次Redis说到底是个缓存，不会有这么多数据造成行高有24层
	Redis可以使用跳表，而且不糊像B+树那也不断维护树的开销。所以Redis可以用跳表，而mysql不可以
 
                   
  好：那么面试我推荐这样去回答，
   B+树是磁盘io友好型数据结构，而跳表是内存友好型数据结构，我想从行高和维护效率这两方面去答
  首先mysql单表2200w数据仅需要3层，对应跳表达到和B+树一样二分效果的话需要24层，这对于磁盘存储的mysql，
   		无疑选择B+树最佳。
  	而Redis是基于内存的，行高不是它的限制，其次Redis是作为缓存 ，数据没那么大，行高也不会那么高
    然后就是维护方面，B+树需要不断的去维护B+树的结构，而跳表这样链表结构，插入和删除是很轻松的。Redis选择跳表性能也
     会有很大提高
                
                   
                   
拓展：
mysql单表2200w数据就要分库分表了，可以通过这个来回答从B+树方面做分库分表的原因。
mysql的innoDB引擎3层的B+树可以存储多少条数据？
首先，
B+树的一个叶子，大小为16kb，对于4个操作系统页，假设一行数据1kb，
那么一个叶子结点就是16行数据
非叶子结点：存放主键和指针
主键类型bigint 占用8字节，innoDB指针占用6字节，也就是一共14字节
单个结点可存放16KB/14byte也就是1170个指针
那么，
	一个结点1170指针，3层b+树，1170*1170*16就是2200w数据

为何说B+树对磁盘io友好？
首先就是B+树叶子形成了有序链表，对于磁盘来说，可以很好的进行预读，利用缓存机制，减少io
其次是B+树叶子大小固定，更好的支持预读，一次读取多个结点到内存，减少io
还有就是B+树叶子不和指针混合，使得分裂合并磁盘io少
                   （这里用刚才教你的三点 从有序链表和叶子这两方面答就ok
叶子方面：叶子只存放数据，大小固定，导致分裂合并io减少，和方便预读，有序链表也可方便预读，减少io

最左前缀原则指的并不是where后面的顺序，而是where后的条件能不能去和联合索引构建的索引去比较
比如，select b,c,d from table where b=1,c=1,d=1
那么d=1,b=1,c=1,也是可以走索引的
bcd联合索引来说1*1 111 11* 1** ，只要能匹配到最左就能走索引，
为啥不能，你看上图的111，如果来一个*11，你怎么去区分是走左树还是右树，所以这样就会去全表扫描了

expalin会做优化，
比如id有10个 id>9肯定是走索引的，但是id<9。走索引再回表，不如直接全表扫描去走的快。

order by
执行计划会分析走索引和直接全表扫描那个性能高
如果select *,那么好处是直接得到排序号的，但是要回很多表去拿数据，全表扫描不需要回表，但是需要内存区排序。
select b,走索引会更快，不用回表，性能比全表扫描快

对字段进行操作
	包括类型转行，+-操作等
	这里点下，mysql编码，a b c这些字符，转换时，都是0
	如果一个字段存放字母，然后查询的时候，比如where a = 1,此时会把字段强转为0，这会破坏B+树，同样修改字段的操作都会这样
	比如a+1 = 1 + 1;这样的条件

B+树索引
hash索引
全文索引

这里强调下B+树的索引。
首先聚簇索引和覆盖索引是两个概念，本身不是索引
B+树的索引有：主键索引、唯一索引、二级索引（也叫辅助索引）
聚簇索引（主键索引、没主键情况下用唯一索引作为聚簇索引、没唯一索引的话用行格式维护的rowid）
非聚簇索引（唯一索引、辅助索引）

聚簇索引  一般是B+树维护的主键索引
没有主键 回去寻找非空的唯一键(注意是非空的唯一键)


每个叶子结点存储了索引列元素，主键一般设为自增的 查询效率高
SELECT * from table where id----》主键   

没有定义主键、没有非空唯一键  mysql会使用rowid作为聚簇索引

就是辅助索引  非主键索引

5个，每个索引一个B+树，还有rowid的聚簇索引

辅助索引使用B+树构建的  叶子结点存的是主键  当需要其他数据的时候
就会回表

何为回表
通过辅助索引获得主键  再通过主键索引来找到完整的行记录

回表会有性能问题

和主键索引一样存放数据的话  空间问题肯定是有的，再者，这些B+树要保证数据的一致性，一个索引的
B+树修改了，辣么其他的都要改，这样就很不明智，
不能为了查询方便就这样搞~，
可以经量的去做到覆盖索引，从而减少回表。

查询优化器会判断那个更快

数据在叶子节点上 每个叶子结点有主键id和对应联合索引的数据，  查询联合索引中
的数据时候   不涉及其他字段的话  不会回表查询

排序的顺序是这样的：
	最佳左前缀
	最左原则  （a,b) 先a再b  再主键索引
联合索引合理运用可以减少回表

B+树查数据  一般3到4次  
热数据-----》hash索引更快
自适应Hash索引
	mysql自己做  开发人员无法控制
	
	5.7以后默认开启

一个索引就是一个B+树 帮助快速定位到数据
一个select一般只使用一个辅助索引   即使用到了多个二级索引

负面：会降低插入速度

让主键索引列的类型尽可能的小
	磁盘io  叶子结点大小限制
	让主键索引列的类型尽可能小，是为了减少主键索引所占用的磁盘空间和所需的内存缓存空间，以及提高查询效率和系统性能。在数据库系统中，主键索引一般采用B+树等数据结构实现，在B+树中，每个节点所能容纳的关键字数是有限制的。如果主键索引列的类型非常大，那么每个节点所能容纳的关键字数就会减少，因此需要更多的磁盘空间来存储索引数据，导致查询效率降低。同时，由于主键索引是辅助索引的基础，辅助索引也会利用主键索引树中存储的键值来定位数据记录，因此主键索引列的类型也会影响到辅助索引的性能。

因此，合理地选择主键索引列的数据类型，能够避免空间浪费，提高查询效率和系统性能。然而，需要注意的是，在选择主键索引列的数据类型时，不应仅考虑节省磁盘空间和提高查询效率，而应根据实际情况、数据类型、数据精度等因素进行选择，保证数据的正确性和查询效率的平衡，以充分发挥主键索引在数据库系统中的作用。

==========================================================================================
索引列的选择
	索引的离散性
		不重复的索引值数/总数   1/N ~1 越高  查询效率越好
		也就是说   元素尽可能的不重复
==========================================================================================		
前缀索引
	展示一部分
	缺点
		无法groupby  orderby   做覆盖索引
	选择
		索引的离散性 
==========================================================================================
只为搜索  排序  分组的字段加索引
==========================================================================================
多列索引创建	
	将离散性最高的放前面
	将频率高的sql做索引、结合实际需求
	
	三星索引
		一星   27
			将查询到的记录连续在一起  宽度越窄
		排序星  23
			索引的顺序 和预期顺序一致   
		宽索引星  50
			做到覆盖索引  不回表
==========================================================================================			
总结
索引的sql调优
	让主键索引列的类型尽可能的小
	选择离散值大的索引列
	只为搜索  排序 分组的字段加索引
	联合索引尽可能做到覆盖索引、注意索引字段的先后顺序，也是根据离散性、结合实际创建（频率
	三星索引原则覆盖索引
	前缀索引