网站开发设计报告怎么写,wordpress鼠标插件,wordpress power,公司网站公司简介1、索引介绍
索引是一种用于快速查询和检索数据的数据结构#xff0c;其本质可以看成是一种排序好的数据结构。
常见的索引结构有#xff1a;B数#xff0c;B树#xff0c;Hash和红黑树等。在MySQL中#xff0c;无论是 InnoDB还是MyISAM#xff0c;都使用了B树作为索引…1、索引介绍
索引是一种用于快速查询和检索数据的数据结构其本质可以看成是一种排序好的数据结构。
常见的索引结构有B数B树Hash和红黑树等。在MySQL中无论是 InnoDB还是MyISAM都使用了B树作为索引结构。
索引的优缺点是什么
优点
使用索引可以大大加快数据的检索速度减少检索量通过创建唯一索引可以保证数据库表中每一行数据的唯一性
缺点
创建索引和维护索引需要耗费时间索引需要使用物理文件存储会耗费一定的空间大部分情况下索引查询都是比全表扫描要快的但是如果数据库的数据量不大那么使用索引也不一定能够带来很大提升
2、索引底层数据结构选型
Hash表
哈希表是键值对的集合通过键key即可快速取出对应的值value因此哈希表可以快速检索数据。
为何能通过key快速取出value这是因为哈希算法通过哈希算法我们可以快速找到key对应的index找到了桶的位置也就找到了对应的value。
但是哈希算法有Hash冲突的问题多个不同的key经过哈希算法可能得到的index相同这就产生哈希碰撞常用的解决方法是链地址法通过将数组的每一个元素作为一个链表将哈希冲突数据存储在链表。
MySQL的InnoDB存储引擎不直接支持常规的哈希索引但是InnDB中存在一种特殊的“自适应哈希索引”自适应哈希索引并不是传统意义上的纯哈希索引而是结合了B Tree 和哈希索引的特点以便更好地适应实际应用中的数据访问模式和性能需求。即哈希数组中每个哈希桶实际是一个小型的BTree结构这个BTree结构可以存储多个键值对而不仅仅是一个键这有助于减少哈希冲突链的长度提高索引的效率
既然哈希表检索数据这么快为什么MySQL没有使用它作为索引的数据结构呢主要因为Hash索引不支持顺序和范围查询 。例如对于查询 id500的数据这种范围查询如果是用二叉树直接遍历比500小的叶子节点就可以但是Hash索引是根据Hash算法来定位需要对1-499的数据都进行一次hash计算来获取每个位置的value
二叉查找树
二叉查找树是一种基于二叉树的数据结构
左子树所有节点的值均小于根节点的值右子树所有节点的值均大于根节点的值’左右子树也分别为二叉查找树
当二叉查找树是平衡的时候查询的时间复杂度为Olog2N具有比较高的效率但是如果二叉查找树不平衡时最坏的情况就是当有序插入节点树就退化成了线性链表查询效率急剧下降时间复杂度退化为ON
二叉查找树的性能非常依赖于它的平衡程度这就导致其不适合作为MySQL底层索引的数据结构
AVL树
自平衡二叉查找树。AVL树的特点是保证任何节点的左右子树高度之差不超过1 因此也被称为高度平衡二叉树它的查找、插入和删除在平均和最坏情况下的时候复杂度都是Olog n AVL树采用了旋转操作来保持平衡主要有4种旋转操作LL旋转RR旋转LR旋转RL旋转。由于AVL树需要频繁地进行旋转操作来保持平衡因此会有较大的计算开销进而降低了查询性能。并且在使用AVL树时每个树节点仅存储一个数据而每次进行磁盘IO时只能读取一个节点的数据如果需要查询的数据分布在多个节点上就意味着要进行多次磁盘IO而磁盘IO是一项耗时的操作。
由于旋转的耗时AVL树在删除数据时效率很低在删除操作较多时维护平衡所需的代价可能高于其带来的好处所以实际情况AVL树使用的并不多
红黑树
红黑树是一种自平衡二叉查找树通过在插入和删除节点时进行颜色变换和旋转操作使树始终保持平衡状态
每个节点非红即黑根节点总是黑色的每个叶子节点都是黑色的空节点如果节点是红色的则它的字节点必须是黑色从根节点到叶节点的每条路径必须包含相同数目的黑色节点即相同的黑色高度 和AVL树不同的是红黑树并不追求严格的平衡而是大致的平衡。红黑树的查询效率稍有下降因为红黑树的平衡性相对较弱可能会导致树的高度较高这可能会导致一些数据需要进行多次磁盘IO操作才能查询到这也是MySQL没有选择红黑树的原因 。红黑树的插入和删除操作效率大大提高了因为红黑树在插入和删除节点时只需进行O1次数的旋转和变色操作即可保持基本平衡状态。
红黑树的应用很广泛TreeMapHashMap等底层都使用到了红黑树对于数据在内存 这种情况来说红黑树的表现还是非常优异的但是对于数据在磁盘等辅助存储设备中的情况 红黑树并不好用因为红黑树长得还是太高了当数据在磁盘时磁盘IO会成为最大的性能瓶颈设计的目标应该是尽量减少IO此时而树的高度越高增删改查所需要的IO次数越多会严重性能
B树B树
B树
B树全称为多路平衡查找树 B树是B树的一种变体。
定义B树最重要的概念是阶数对于一颗m阶B树需要满足以下条件
每个节点最多包含m个子节点如果根节点包含子节点则至少包含2个子节点除根节点外每个非叶节点至少包含m/2个子节点拥有k个子节点的非叶子节点将包含k-1条记录所有叶节点都在同一层
B树的优势除了树的高度小还有对访问局部性原理的利用。所谓局部性原理是指当一个数据被使用时其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点当访问其中某个数据时数据库会将该整个节点读到缓存中 当它临近的数据紧接着被访问时可以直接在缓存中读取无需进行磁盘IOB树的缓存命中率更高
MongoDB的索引使用的就是B树。
B树和B树的区别 B树的所有节点既存放键也存放数据而B树只有叶子节点会存放键和数据其他节点只存放key B树的叶子节点是独立的B树的叶子节点有一条引用链指向与它相邻的叶子节点 B树的检索的过程相当于对范围内的每个节点的关键字做二分查找可能还没到达叶子节点检索就结束了B树的检索效率很稳定任何查找都是从根节点到叶子节点的过程 B树中进行范围查询时首先找到要查找的下限然后对B树进行中序遍历直到找到查找的上限而B树的范围查询只需要对链表进行遍历即可 B树一个节点中可以有很多个元素元素是有序的 B树一个节点中可以有很多个元素有序的叶子节点之间有指针指向相邻的叶子节点非叶子节点的元素都会冗余一份在叶子节点
在MySQL官网中是这么介绍的 将节点比作是page事实上也确实是以页为单位root page point to the leaf pages ; leaf pages can also point to each other 根节点会指向叶子节点叶子节点之间也会有指针指向彼此双向的指针
B树与B树相比具备更少的IO次数更稳定的查询效率和更适合范围查询这些优势
为什么B树索引能加快访问的速度
因为存储引擎不再需要进行全表扫描来获取需要的数据取而代之的是从索引的根节点开始进行搜索根节点的槽中存放指向子节点的指针存储引擎根据这些指针向下层查找。
什么时候用B树索引
B树索引适用于全键值、键值范围或者键前缀查找 。其中键前缀查找只适用于最左前缀的查找。
B树索引和哈希索引的明显区别是
如果是等值索引那么哈希索引明显有绝对优势因为只需要经过一次哈希算法即可找到相应的键值前提是键值都是唯一的如果键值不是唯一需要先找到该键所在位置然后根据链表往后扫描直到找到相应的数据
如果是范围索引哈希索引就没有用了。因为原先是有序的键值经过哈希算法后有可能变成不连续的了就没办法再利用索引完成范围查询检索
哈希索引也没办法利用索引完成排序以及like‘xxx%’这样的部分模糊查询这本质上其实也是范围查询
B树索引的关键字检索效率比较平均在有大量重复键值情况下哈希索引的效率也是很低的因为有哈希碰撞的问题。
在MySQL中只有 HEAP / MEMORY 引擎表才能显式的支持哈希索引在HEAP表中如果存储的数据重复度很低对该列数据以等值查询为主没有范围查询、没有排序 特别适合采用哈希索引
InnoDB引擎则是采用B树的索引结构。这也是大部分数据库引擎的索引结构。B树索引适用于绝大数场景。
3、InnoDB中的B树是怎么产生的
InnoDB中一页多大InnoDB_page_size 16384 ~ 差不多16kbInnoDB存数据时先要在内存中开辟至少一页的内存16kb然后当要存入磁盘时是一页一页的存从磁盘里读取数据时也是一页一页的读使用page这样的逻辑单位可以减少io次数提高查询效率当插入多条数据时即便没有设置主键自增不按主键大小顺序插入时查询到的所有数据的结果却发现是按照主键递增的顺序返回结果 这是为什么
因为InnoDB在插入数据时就会进行排序。当插入用户数据时会根据主键的大小按照递增的顺序来插入到用户数据区域形成一个链表这样的好处是**当下次查询一个元素时可以通过比较大小很快确定元素在的位置不用遍历全部的元素 ** 但是插入的效率会有所降低因此用innoDB时建议设置主键自增这样会优化插入性能。非自增的话每次插入都要比较id来插入到数据区域经常要打乱原来的顺序这样性能肯定会下降。
InnoDB中的B树的产生
接回上面当用户数据区域链表越来越长时这时候查询效率就会变的很低如何解决呢InnoDB的优化策略是加上一个页目录页目录是将用户数据区域分组“组长”便是这组中主键值最小的将它放入到页目录中这样就将用户数据区域分为一组一组的当再次查询数据时先查页目录和页目录中的值比较大小以确认在哪个分组然后在数据区域里找到数据 如下图 当这一页都插满了之后就会再开辟一页然后继续按照这样的数据结构来排序这一页其实就是一个节点 。页与页之间会有指针指向下一页如下图 当数据非常多开辟的页节点也越来越多这个时候又形成一个很长很长的页链表InnoDB同样选择再加一层来进行优化。再分出一层来存储页的分组。将每一页的页目录的最小值存在新加的一层当查询数据时从上往下查减少遍历次数提高查询效率 看得出这其实就演变成了一颗B树。这是一个两层的B树同理当数据越来越多继续往上面加层数每一页就是一个leaf page 上面的是root page 。这样就解释了为什么MySQL官网中将节点叫做页因为页才是最恰当的。同样这也解释了为什么非叶子节点的元素的值都会在叶子节点冗余一份因为根节点的值就是取自于叶子节点查询时从上往下不断确定分组–确定页。
4、InnoDB如何支持范围查找能走索引 叶子节点存储的是完整数据称为数据页 而非叶子节点存储的是索引称为索引页 如上面生成B树的例子中存的是主键索引。找到了索引也就找到了数据这就是聚簇索引 主键索引就是一种聚簇索引一般情况下主键会默认创建聚簇索引且一张表只能有一个聚簇索引。当查询时根据的字段是索引时是从上往下查询走索引的可以迅速确定到页然后找到数据这样会非常的快就能查找到数据
非范围查询如 select * from user where id 6 ; 根据索引页直接找到id6在哪一页然后找到数据
范围查询如 select * from user where id 6;先执行id6时的操作利用索引然后在数据页中大于就往右走小于就往左走----这就是为什么说数据页之间是双向链表 。因此根据索引范围查询也是走索引的
而当查询的字段根据的是非索引字段时不能从索引页查而是从叶子节点数据页查找 一条一条的遍历—这称为全表扫描因此对于经常要查询的字段建议加上索引能极大的提高查询速度
5、为什么要遵守最左前缀原则才能利用到索引
什么是最左前缀匹配原则
最左前缀匹配原则是指在使用联合索引时MySQL会根据联合索引中的字段顺序从左到右依次到查询条件中去匹配如果查询条件中存在 与联合索引中最左侧字段相匹配的字段就会使用该字段过滤一批数据直至联合索引中全部字段匹配完成。所以与where语句后面的查询字段的顺序没有关系是根据联合索引里从最左边的字段来看查询条件里有没有相匹配的字段
在使用联合索引时B树的存储时这样的这也叫作非聚簇索引辅助索引 用InnoDB时建议用主键自增这样会优化插入性能。非自增的话每次插入都要比较id来插入到数据区域经常要打乱原来的顺序这样性能肯定会下降。
例如现在联合索引的字段是abc那么索引页存储的是联合字段的值 数据页存储的是 联合索引字段的值和主键值 。这样的目的是什么呢
当查询 select * from user where a1and b1and c1时先根据索引页找到索引为111的页然后在数据页中根据主键1回表到主键索引表中的数据页找到这条数据行。辅助索引访问数据总是需要二次查找第一次找到主键值第二次根据主键值找到具体的数据行
那么为什么不遵循最左前缀原则就会导致索引失效用不上索引
不遵循最左前缀原则其实就是你给的查询条件的字段都不匹配联合索引的最左的字段。也就是说当联合索引是abc时你的查询条件里没有根据a字段例如bc这时是无法从索引页开始查找的因为是从联合索引的第一个字段开始查询而第一个字段就不匹配就走不了索引页了 只能从数据页一条一条查找–全表扫描。
注意查询条件的字段顺序和联合索引的字段顺序不一致是没有关系的 因为是根据联合索引的字段开始从最左端匹配只要提供了联合索引最左端得到字段就遵循了最左前缀原则
6、为什么范围查找会导致索引失效
对于查询并不一定就是走索引快。
例如联合索引bc d现在要查找 select * from user where b1。如果从索引开始找可不可以呢当然可以这是遵循最左原则。查找时先从索引页开始找找到b1的然后到数据页找b1的主键的值然后回表查询 这些主键所对应的数据的全部字段。这样一定是最快的吗要知道任何查询都有一种方式是全表查询在这个查询情况下如果直接全表查询就是将所有的数据页一页一页的遍历遍历完就能查询到在这种情况全表查询效率要比索引查询还快因此索引就失效了InnoDB会选择走全表查询
所以是否走索引要根据情况而定并不是什么时候走索引都是最快的
范围查找时给的查询条件更精确一点利用索引会更快
7、覆盖索引是什么
例子还是上面的联合索引bcd当查询条件为 select b from user where b1;
对于这样的查询走索引的话先从索引页找到b1然后在数据页中找到b1的页这个时候因为我们要查找的是b 而不是要所有。而b字段的值就是在数据页中保存不需要通过主键去主键索引里回表查询直接就能查找到b1的b的数据这就是覆盖索引。这样是很快的。如果select a 呢也是覆盖索引a是主键在数据页中存的是主键的值和联合索引的值因此查a的话也不需要去回表可以直接查找到这就是覆盖索引。不需要二次回表查询
当查询语句为select b from user; 这种情况数据库又是如何查询的呢
没有查询条件那么是不是就一定不用索引走全表扫描其实不是的。InnoDB会比较性能。第一种当然就是全表扫描扫描主键索引的叶子节点一页一页的扫描然后将字段b的所有数据查询出来第二种是在b,c,d联合索引中叶子节点存储的联合索引的值和主键值扫描联合索引的叶子节点同样可以将b的所有数据查询到。但是联合索引中的叶子节点保存的是不完整的字段—只有联合索引字段和主键 而主键索引的叶子节点保存的是完整的数据 那么联合索引的叶子节点相比主键索引页数会更少查询当然会更快。因此这种情况下InnoDB依旧是走索引查询–bcd联合索引。
8、order by 为什么会导致索引失效
当查询语句为 select * from user order by (b,c,d);
一样的会有两种走法比较性能然后选择性能高的
走全表扫描—主键索引的叶子节点需要额外排序但是不用回表走索引扫描—联合索引b,c,d的叶子节点因为没有where查询所以不能从上往下只能扫描叶子节点。此时是不需要排序的因为叶子节点就是按照索引排序的但是因为查询的是*需要回表查询找到相应的主键然后回表查出所有数据八条数据就需要回八次表
那么哪种更快呢当数据量少的时候显然全表扫描会更快一点虽然要额外排序但是因为数据少所以排序的时间非常短和回八次表相比是很微小的因此这种情况InnoDB也会选择走全表扫描索引失效
但是当改为 select b from user order by (b,c,d);
这个时候全表扫描还是像上面那样的步骤但是索引扫描就省去了回表这一操作所以肯定会走索引
需要二次回表的话直接走全表会更快而不需要二次回表走索引更快
9、关于字段的数据类型转换导致索引失效
int a
varchar b
a是主键现在建立b的索引
select * from user where a 1—会走索引
select * from user where b “1”—会走索引
select * from user where a “1”—会走索引
select * from user where b 1—不会走索引
对于第一种和第二组当然没问题会走索引a是int类型查询a1的数据走主键索引b是字符串类型查询b“1”的数据走b索引
而对于第三种情况a是int类型现在查询条件是有没有a等于一个字符串的数据这个时候InnoDB会将“1”转化为数值类型的1 然后查询a1所以也会走主键索引
对于第四种情况同样要将字符转换为数值这里要做的是把这个“字段”转化为从varchar转换为int如何把字段转化为数值呢需要把b字段的所有字符数据都转换为int类型 这可不是一个小工程是很难办到的并且会改变索引的b树因为b索引的b树里存的是字符现在要改为对于的int数字这样显然是非常耗内存和性能的。因此InnoDB走的是全表扫描不走索引。
在InnoDB中涉及对字段进行操作包括查询条件包含a1之类的字段操作都会导致用不了索引
10、MySQL聚簇索引和非聚簇索引的区别
都是B树的数据结构。
聚簇索引
聚簇索引将数据存储和索引放在一起如根节点索引页放索引叶子节点数据页放数据 并且是按照顺序组织找到索引也就找到了数据数据的物理存放顺序与索引顺序是一致的。即只要索引是相邻的那么对应的数据一定是相邻地存放在磁盘上的。主键索引就是聚簇索引 InnoDB一定有主键—如果不主动设置则会使用unique索引没有unique索引则会使用数据库内部的一个行的隐藏idDB_ROW_ID来当做主键索引。 优势
查询通过聚簇索引可以直接获取数据相比非聚簇索引需要二次查询效率没有索引覆盖的情况更高
聚簇索引对于范围查询的效率更高因为其数据是按照大小排列的
聚簇索引适合用在排序的场合
劣势
依赖于有序的数据因为B树是多路平衡树如果索引的数据不是有序的那么就需要在插入时排序如果数据是整型还好如果是类似于字符串或UUID这种又长又难比较的数据插入或查找的速度会非常慢
更新代价大如果对索引列的数据修改时那么对应的索引也将会被修改而且聚簇索引的叶子节点还存放着数据修改代价很大。所以对于主键索引来说主键一般都是不可修改的。
维护索引很昂贵特别是插入新行或者主键被更新导致要分页的时候
非聚簇索引
非聚簇索引也叫作辅助索引索引结构和数据分开放。叶子节点存储的不是数据而是数据行的地址存储索引和主键 根据索引查找到数据行再根据数据行的位置去磁盘查找数据。即先根据索引找到叶子节点中的位置然后根据主键回表主键索引查询。这种相当于是建立在主键索引之上因此也叫作辅助索引。MySQL的MyISAM引擎不管是主键还是非主键使用的都是非聚簇索引 优点
更新代价比聚簇索引要小因为非聚簇索引的叶子节点并不存放数据
缺点
依赖于有序的数据跟聚簇索引一样非聚簇索引也依赖于有序的数据。
二次回表当查到索引对应的指针或主键后需要根据指针或主键再到数据文件或表中查询。回表查询
11、正确使用索引
1、选择合适的字段创建索引
不为NULL的字段索引字段的数据应该尽量不为NULL因为对于数据为NULL的字段数据库较难优化被频繁查询的字段我们创建索引的字段应该是查询操作非常频繁的字段被作为条件查询的字段被作为where条件查询的字段应该被考虑建立索引频繁需要排序的字段索引已经排序这样查询可以利用索引的排序加快排序查询时间被频繁用于连接的字段经常用于连接的字段可能是一些外键列对于外键列并不一定要建立外键只是说该列涉及表与表的关系。对于频繁被连接查询的字段可以考虑建立索引提高多表连接查询的效率
2、被频繁更新的字段应该甚至建立索引
虽然索引带来的查询上的效率但是维护索引的成本很大。如果一个字段不经常查询反而经常要更改那么不应该建立索引
3、限制索引数量
所有并不是越多越好建议单张表索引不超过5个
索引可以提高查询效率但同样会降低插入和更新的效率甚至有些情况并不会提高查询效率。因为MySQL优化器在选择如何优化查询时会根据统一信息对每一个可以用到的索引进行评估以生成出一个最好的执行计划如果同时有多个索引都可以用于查询就会增加MySQL优化器生成执行计划的时间同时会降低查询性能
4、尽量考虑建立联合索引而不是单列索引
因为索引是需要占用磁盘空间的可以简单理解为每个索引都对应着一颗B树 如果一个表的字段过多索引过多那么当这个表的数据达到一个体量后索引占用的空间也是很多的的且修改索引时耗费的时间也是较多的如果是联合索引多个字段在一个索引上那么将会节约很大的磁盘空间 修改数据的操作效率也会提升
5、避免冗余索引
冗余索引指的是索引的功能相同能够命中索引a,b就肯定能命中索引a那么索引a就是冗余索引。在大多数情况下都应该尽量扩展已有的所有而不是创建新索引
6、避免索引失效
索引失效也是慢查询的主要原因之一常见的导致索引失效的情况 范围查找导致索引失效select * …where xxx where查询范围过大导致没有走索引而是全表查询。where后的条件尽量精确一点 创建了联合索引但查询时没有遵循最左匹配原则 在索引列上进行计算、函数、类型转换等操作 以 %开头的LIKE查询比如 like ‘ %abc’ ----全表扫描索引失效 查询条件中使用or且or的前后条件中有一个列没有索引涉及的索引都不会被使用到。 使用order by导致索引失效。没有where语句时对于非聚簇索引只能从叶子节点开始查找找到对应主键然后回表查询这样效率不如直接全表扫描所以索引失效
7、删除长期未使用的索引
不用的索引会造成不必要的性能损耗所以要删除长期未使用的索引。MySQL5.7可以通过查询sys库的schema_unuser_indexes视图来查询哪些索引从未被使用
