Mysql--索引篇

为何选B+

• hash：无序无法范围。
• 二叉树：不平衡。
• 平和二叉：旋转效率低，IO效率不高。
• 红黑：IO效率不高，顺序插入会倾斜。
• B+：降低高度，进一步优化

  索引简介

  索引是一种利用某种规则的数据结构与实际数据的关系加快数据查找的功能索引是数据库底层软件组织，DBMS使用数据索引进行创建、查询、更新和删除数据。不同的存储索引引擎提供不同的存储机制、索引技巧、锁定水平等。使用不同的存储索引，还可获得特点的功能。

建立原则

• 定义主键的数据列一定要建立索引。
• 定义有外键的数据列一定要建立索引。
• 对于经常查询的数据列最好建立索引。
• 对于需要在指定范围内的快速或频繁查询的数据列;
• 经常用在WHERE子句中的数据列。
• 经常出现在关键字order by、group by、distinct后面的字段，建立索引。如果建立的是复合索引，索引的字段顺序要和这些关键字后面的字段顺序一致，否则索引不会被使用。
• 对于那些查询中很少涉及的列，重复值比较多的列不要建立索引。
• 对于定义为text、image和bit的数据类型的列不要建立索引。对于经常存取的列避免建立索引。
• 限制表上的索引数目。对一个存在大量更新操作的表，所建索引的数目一般不要超过3个，最多不要超过5个。索引虽说提高了访问速度，但太多索引会影响数据的更新操作。
• 对复合索引，按照字段在查询条件中出现的频度建立索引。在复合索引中，记录首先按照第一个字段排序。对于在第一个字段上取值相同的记录，系统再按照第二个字段的取值排序，以此类推。因此只有复合索引的第一个字段出现在查询条件中，该索引才可能被使用,因此将应用频度高的字段，放置在复合索引的前面，会使系统最大可能地使用此索引，发挥索引的作用

  分类

  -- 主键索引：根据主键建立，非空非重复。
  ALTER TABLE 'tablename' ADD PRIMARY KEY py_index('col');
  -- 唯一索引：索引列唯一非空
  ALTER TABLE 'tablename' ADD UNIPUE index_name('col');
  -- 普通索引：无限制
  ALTER TABLE 'tablename' ADD INDEX index_name('col');
  -- 全文索引：用大文本对象的列构建的索引
  ALTER TABLE 'tablename' ADD FULLTEXT ft_index('col');
  --  组合索引：
  ALTER TABLE 'tablename' ADD INDEX index_name('col','col1','col2');
  --最左前缀原则：把最常用作检索或排序的列放在最左，依次递减，组合索引相当于建立
  --了“col;colcol1;colcol1col2”三个索引，col1;col2时不能使用索引的。

  创建

  --建表时创建
  CREATE TABLE mytable(  
  ID INT NOT NULL,   
  username VARCHAR(16) NOT NULL,  
  INDEX [indexName] (username(length))  
  ); 
  --建表后添加
  ALTER TABLE my_table ADD [UNIQUE] INDEX index_name(column_name);
  --或者
  CREATE INDEX index_name ON my_table(column_name);
  --删除
  DROP INDEX my_index ON tablename；
  --或者
  ALTER TABLE table_name DROP INDEX index_name;
  --查看
  SHOW INDEX FROM tablename ;

  索引失效场景

• “%” 开头的LIKE语句，模糊匹配。
• OR语句前后没有同时使用索引。
• 数据类型出现隐式转化（如varchar不加单引号的话可能会自动转换为int）
• 索引列做计算会失效
• 索引列使用内置函数会失效

• 索引不会包含null值的列。

  索引不足

• 降低更新表的速度。

• 占用空间，尤其大量索引或大量组合索引，索引文件膨胀很快。
• 维护成本随着数据增大而增大

• 降低修改操作的效率，修改时还要修改索引表

  数据引擎

• MyISM

  查找：性能极佳。 存储：myisam在磁盘上存储上有三个文件.frm(存储表定义，创建表的语句) .myd（表数据） .myi（表索引文件）MyISAM的主索引和数据是分开的（非聚集索引方式(叶子节点存地址/id，找到叶子还要再找数据)），保存表具体行数；innodb不保存。 锁：MyISAM使用的是表级锁不支持高并发，以读为主。 事务：MyISAM没有事务支持和MVCC全文索引：MyISAM支持FULLTEXT类型的全文索引。 主键：MyISAM允许没有任何索引和主键的表存在，索引都是保存行的地址 外键：不支持

• InnoDB

  存储：innodb磁盘上存储的是表空间数据文件和日志文件，innodb表大小只受限于操作系统大小，数据文件本身就是主索引文件。InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。生成的文件frm（表结构，创建语句）、idb（数据+索引，聚集索引方式）。 锁：InnoDB支持行锁（共享锁、排他锁）粒度更小，但执行时不能确定扫描范围同样锁全表。 事务：InnoDB支持ACID兼容的事务事务和MVCC。 全文索引：InnoDB不支持FULLTEXT类型的全文索引，但是InnoDB可以使用sphinx插件支持全文索引，并且效果更好。 主键：InnoDB如果没有设定主键或非空唯一索引，就会自动生成一个6字节的主键，数据是主索引的一部分，附加索引保存的是主索引的值。 外键：支持

InnoDB索引详解、聚簇索引、主键索引、索引覆盖（覆盖索引）

InnoDB为每个索引维护一个独立的B+树。 innodb引擎最小的存储单元是页（page），一页大小是16K.ext4文件系统的最小单元是块，一块4K，磁盘一个扇区大小512字节。 指针在innodb中大小为14字节。 假设一条记录1K一个块（叶子）存16个，非叶子存指针=（16/指针大小），行高3即可上亿。

• 主键索引又称聚集索引，是InnoDB的重要索引结构，主键索引是一个B+树，子节点存储索引节点信息和关联，叶子节点存储主键索引信息+数据信息，叶子节点按照主键索引有序排列的，查找块。
  • 若没有设置主键索引，默认第一个非空的唯一索引为聚集索引；若唯一索引也没有，数据库回自动生成隐藏的row-id组建聚集索引。

• 非聚集索引：普通索引或复合索引，节点存储的是具体的索引字段信息，叶子节点存储主键索引+数据，查找时先在非聚集索引中找到对应的主键，再根据主键索引查找对应的数据，等于走了两遍B+树，不如主键索引快。
• 覆盖索引：若查询的列全部匹配索引关键字，则直接返回对应索引的数据，那么此时就不用在根据索引的主键在聚集索引中找一遍，减少IO操作。如建立组合索引index(name,addr)，索引叶子节点中会存索引自读那+数据，查询name，addr字段可在索引关键字中直接找到，符合覆盖索引的定义。
• 回表查询：InnoDB引擎中，非主键索引查找数据时需要先找到主键，再根据主键查找具体行数据，这种现象叫回表查询

底层选择

磁盘IO预读

内存分析：内存储器、外存储器，内存块、小、贵、断电丢失；外存即为磁盘读取，机械运动，每次分寻道时间、旋转延迟、传输时间三部分。考虑到磁盘IO很昂贵，计算机做了优化，每次IO会把目标地址相邻的数据也读取到内存缓冲区，局部预读性原理告诉我们，当计算机访问一个地址的数据时，相邻数据也会被访问到。

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。 InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小。

• 数据结构

  哈希表、二叉搜索树（BST）、自平衡二叉查找树（AVL）、红黑树(RBT)、B数和B+树

• 哈希表hash

  哈希表是索引利器，直接把值通过哈希函数转换为固定长的key地址，通过地址进行查找。但是无限的数据去映射固定长的哈希，会存在哈希碰撞。不同的值会计算出同一个结果。 解决碰撞的创建方法是链地址法，通过链表把碰撞的数据连接起来，如果存在碰撞，遍历链表。 哈希的算法复杂度为O（1），但是考虑到数据检索的常用操作是范围查找，mysql没有采用哈希做索引结构。使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找。

二叉搜索树(BST)

二叉的算法复杂度是O(logn)，二叉理想情况如图查找7个数据最多比较3次，也解决了哈希无法解决的范围查找问题但是二叉有个缺点，极端情况下会退化为链表。

红黑树(RBT)

红黑树排序规则左小右大。红黑树的时间复杂度为O（logn）比如从1到7升序插入数据，普通二叉会退化为链表，但是红黑树会不断调整状态， 红黑树有着不错的性能，但是当大量数据顺序插入时，红黑树会出现倾斜，并没有完全解决二叉树的问题

AVL自平衡二叉树(AVL)

二叉树通过自动旋转和调整，能让二叉树始终保持基本的平衡状态，这样就能保持二叉树的最佳性能，这类树有AVL和红黑树。 AVL比红黑树更为严格，在AVL树中任何节点的两个子树的高度最大差别为1，是高度平衡的二叉树，1-16顺序插入依然能够保持平衡

• 但是AVL也不适合Mysql的索引数据结构，这次是在IO上。数据库查询数据的瓶颈在磁盘IO，如果使用AVL，我们每个树节点只存储了一个数据，一次磁盘IO只能取出一个节点的数据加载到内存，查几次就要进行磁盘IO几次，消耗大量时间。
• 磁盘IO的特点是：读取1B和1KB数据所消耗的事件是基本一样的，针对这个特性，节点上尽可能的多放数据就可大大提升效率。
• B和B+树就是这个设计原理。

B树(平衡多路查找树)

B-Tree是为磁盘等外存储设备设计的一种平衡查找树。系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的， 位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。 InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。 InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小。 B树的查找性能为O（h*log N）h为树高，N为每个节点关键词的个数，可提高I/O效率，加快检索速度。 B树的每个节点的元素可视为一次IO读取，树的高度表示最多的IO次数，如图，每个节点限制最多存储两个key，key超过限制就会自动分裂 但是由于每次IO读取1B、1KB时间基本一样，可以优化为每个节点最多6个数据

B+树

B树已经很优秀了，B+树与B树的区别在于B+树的节点存的是索引（地址），B树节点存储数据个数受数据大小限制，B+树的节点可以存储很多索引，B+树的叶子节点存所有的数据。B+树的叶子节点是数据阶段用了链表串联起来，便于范围查找。 B+树在单节点存储有限的情况下存储地址，使树的高度大大降低，减少了磁盘IO；其次叶子节点是真正存储数据的地方，用链表连接，这个链表本身就是有序的，范围查找更有效率，所以Mysql选择了B+树作为索引结构。 B+对比B的优点： 1.磁盘读写代价低， 2.效率稳定，非终点节点存放叶子节点关键字的索引，所以任何关键字的查找必须走一条从根节点到叶子节点的路，所以关键字查询的路径长度相同，导致每个数据的查询效率相当。 3.便于范围查询，B提高了IO性能并没有解决元素遍历的效率低下的问题，B+只需遍历叶子节点就可实现整棵树的遍历，数据库范围查询是频繁的，B-tree的效率太低。补充：B树的范围查找是中序遍历，而B+树是链表遍历；B+劣势：查找结果不成功不如B，内存中B+没有优势，磁盘中有优势。

索引最终选择B+树的原因:

• hash很快，但每次IO只能取一个数，不能范围。
• AVL和红黑树，在大量数据的情况下，IO操作还是太多。
• B树每个节点内存储的是数据，因此每个节点存储的分支太少,B+磁盘读写代价低。
• B+节点存储的是索引+指针(引用指向下一个节点)，可以存储大量索引，同时最终数据存储在叶子节点，并且有引用横向链接，可以在2-3次的IO操作内完成千万级别的表操作。
• 索引是是自增长数字，这样适合范围查找。