标签：存储 查询 索引 详解 键值 数据 节点

关于索引需要理解的几个点

1. 为什么要用索引？

2. 创建索引有哪些缺点？

3. 数据库索引的原理，为什么要用 B+树，为什么不用二叉树？

4. 为什么推荐使用整型自增主键而不是选择UUID？

5. 为什么InnoDB非主键索引结构叶子节点存储的是主键值？

6. 为什么Mysql索引要用B+树不是B树？

7. 为何不采用Hash方式？

8. 什么是Mysql的回表，与索引覆盖之间的关系？

9. 哪些情况需要创建索引？

10. 哪些情况不需要创建索引？

11. 建索引要遵循哪些原则？

索引是什么

官方：索引是帮助Mysql高效获取数据的一种数据结构，而且是排好序的数据结构，索引存储在磁盘文件里； 一句话概括：索引即数据，数据即索引。

不同数据结构实现索引的性能以及优缺点

对于数据库而言，重要的不是数据量，而是当数据量增加时运算如何增加。 如果要处理2000条元素：

• O(1) 算法会消耗 1 次运算

• O(log(n)) 算法会消耗 7 次运算

• O(n) 算法会消耗 2000 次运算

• O(n*log(n)) 算法会消耗 14,000 次运算

• O(n^2) 算法会消耗 4,000,000 次运算

数据在磁盘上的分布不是连续的，如果我们的数据是以我们看到的二维矩阵的形式来存储的，则查询一条数据，理论上需要O(n)次的磁盘IO，这性能可想而知的差，因此需要借助一些数据结构，来提高运算的效率（本质：尽可能多的减少磁盘IO） 数据源：假设有一张一个以自增id为为主键的表，存储了若干条数据。

二叉搜索树

数据结构特点：

（1）若它的左子树不空，则左子树上所有结点的值均 小于 它的根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均 大于 它的根结点的值； （3）它的左、右子树也分别为二叉排序树；
假设我们要查询id=7的数据，对于二维矩阵，则需要7次磁盘IO，才可以取出对应的数据，而对于上图的二叉搜索树，则只需要3次磁盘IO即可查询，依次对应的查询顺序为：4->6->7； 因为二叉搜索树在新增数据的时候，要严格按照它本身的性质，所以下面来两场场景决定了它依然不是最适合索引的结构： （1）由于二叉树本身也是二叉树结构，每个节点只能有两个叶子节点，因此当数据量越来越大时，树的高度也会越来越大，对应的就是不断增加的磁盘IO； （2）当一些表是以自增Id为主键时（或数据是单调的），会出现下列极端情况，此时的二叉树就变成了线性的了，查询效率就变成了O(n)；

红黑树：

数据结构特点：

（1）根节点是黑色； （2）每个节点是黑色或者是红色； （3）每个叶子节点（NIL）是黑色[注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]； （4）如果一个节点是红色的，则它的子节点必须是黑色的； （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点；   缺点：   （1）红黑树（包括平衡树）虽然解决了数据线性的问题，但它依然是一棵二叉树，当数据量太大时，还是无法解决高度的问题；   （2）当数据量增加时，数据新增/更新时，自身的旋转也会带来性能上的挑战；  

B树

数据结构特点：

（1）任意节点的子树的高度差都小于等于1； （2）一个节点可以存储多个键值和数据（包含指向下一个节点的指针，索引值-Key，对应的行数据Data），从左到右按照ASCII码升序排序以及指向子树根节点的指针； （3）每个节点有个度（Degree）的概念，每个节点所存储的Key的数量是Degree - 1，当超过节点最大的度，则会发生拆分/合并； 如图是一个最大度（Degree）为5的一个二阶平衡树，当我们在新增一个节点11时，由于p2指针指向的页数据已满，则会发生一次拆分合并，生成如下结构： 拆分合并的逻辑如下： a.先将节点11插入到10后面，发现超过最大度，则将该节点的数据一分为二； b.将数据9拿到根节点，此时根节点不会超过最大度，满足，并将新生成的指针p3，指向新生成的数据页； 新增数据逻辑如下： a.基于上图，在添加一个节点9，从根节点键值依次比较，发现6小于9且小于等于9，取p2指针指向的数据页； b.从左往右比较，发现9比8大，则新增到8后面（如果此时超过最大度，则会继续发生拆分合并），则生成如下B Tree； 优点： 相对于二叉搜索树和AVL树，在存储同样多数据的情况下，B树的高度更矮，意味着检索需要的磁盘IO次数更少； 缺点： （1）Mysql的每一个节点对应磁盘的一个页，每页大小16K，因此每个节点存储的数据是有限的，即最大度是有限的（具体也和表字段的大小有关系）； （2）当进行范围查询时，B树采用的是中序遍历的方式（因为B树也是遵循了二叉搜索树左子树的值小于根节点，右子树的值大于根节点，多叉树则是通过区间和指针来实现），可能会发生多次的磁盘IO，性能会略差一些；

B+树

数据结构特点：

（1）非叶子只包含键值以及指向下个节点的指针，而所有的数据记录项则存储在叶子节点； （2）叶子节点的数据依照关键字做好了顺序排列； （3）所有叶子节点之间有通过双向链表来连接； B+树相对于B树解决了哪些问题： （1）单一节点由于只存储了键值，没有存储数据，使得节点存储的元素更多，因此同样的数据量，B+树会比B树"更矮"、"更胖"，意味着查询的IO次数更少； （2）所有的查询必须查询到叶子节点（因为所有的数据都存储在叶子节点），查询会更稳定。（B Tree是根据不同的数据有不同的性能表现，例如数据出现在根节点，就只需一次IO；出现叶子节点，就需要m次IO；性能是不固定的。） （3）所有的叶子节点形成一个有序的链条，便于范围查询。（相对于B树的中序遍历，链表的形式效率更高）。

什么是Mysql的回表查询

索引的划分

索引从数据结构的角度划分：

• B+树索引

• Hash索引

• 全文索引

• 空间数据索引（用于地理数据索引）

从物理存储的角度来划分：

• 聚集索引（聚簇索引）

• 非聚集索引（非聚簇索引）

从逻辑的角度划分：

• 主键索引

• 普通索引（单列索引）

• 多列索引（复合索引、联合索引）

• 唯一索引（值必须唯一）

• 空间索引（对空间类型字段建立的索引）

聚集索引和非聚集索引的差别

聚集索引：主键作为键值，叶子节点存储了所有的数据； 非聚集索引：非主键字段作为键值，叶子节点不存储数据，而是存储对应的主键值，想要查找数据的时候，根据查询到的叶子节点的主键值，再去聚集索引中查询数据。 非聚集索引根据主键值去聚集索引查询数据的过程，称为回表； 索引覆盖：不需要回表操作就能获得查询数据，即查询的列要被索引覆盖； 引申问题：为什么非聚集索引的叶子节点不存储数据？直接存储数据查询岂不是更快？

透过B+树理解常见索引优化的本质

常见需要创建索引的场景

1. 主键自动建立唯一索引；
   1. 聚集索引具有唯一性，将索引和数据结构放在一起，因此一个表仅有一个聚集索引；
   2. 如果表没有这样的唯一字段，InnoDb引擎也会默认顶一个主键来作为聚集索引；
     引申问题：为什么建议使用自增id作为主键而不选择uuid；

2. 频繁作为查询条件的字段；
   1. 比如以Name字段作为查询条件，创建以Name字段的非聚集索引；
   2. 若不走索引，则会全表扫描；
   3. 当创建索引后，叶子节点存储的姓名是按Ascii码排序好的，假如查询到的主键依次为3，6,1,2,10，则取出最小主键1，回表查询聚集索引，找到主键1所在的叶子节点，由于聚集索引的叶子节点全部是按升序排列且用链表项链，则可顺序查找到剩余主键值的信息，无需全表扫描；

3. 比如订单表的主键订单id与订单明细表的订单d，建议明细表的订单id建立索引；
4. Select o.id,d.id

  from Order o   Left join OrderDetail d on o.id = d.OrderId

3. 上面的查询中Order表为驱动表，OrderDetail表为被驱动表；
4. 假设Order表有N行数据，OrderDetail有M行数据（为了计算方便，假设两个表的是一对一），则关联列有索引扫描的行数是2*N，没有索引则是N*M次

引申问题：为什么要小表驱动大表   提示：N+N*2*log2M（N为驱动表行数，M为被驱动表行数）

4. 查询中排序的字段，排序字段通过索引访问大幅度提高排序速度；
   1. 因为一个字段建立索引以后，叶子节点都是顺序的，因此这样的字段做排序取值会比无序的形式更快；

常见不需要创建索引的情况

• 表记录太少；
  1. 索引本身需要占物理空间；
  2. 且添加和修改元素都需要维护索引结构；
  3. 对于数据量小的表，查询效率提升与牺牲的代价不划算；
• 经常增删改的表（频繁更新的字段不适合创建索引）；
  1. 创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加，若频繁的发生增删改的动作，B+树结构的维护（IO负担）也是一块性能的开销；
• 数据库重复且分布均匀的表字段
  1. 类似"性别"这一类字段，不建议创建索引，即使创建索引，最终查询出来的主键值也接近均匀分布，相当于全表扫描，相对于维护索引的代价这点性能的提升不划算；

性能分析手段

  慢查询

  MySQL提供的一种日志记录，用于记录MySQL中响应时间超过阈值的语句，具体指运行时间超过 long_query_time 值的收起来，会被记录到慢查询日志中。   long_query_time 的默认值为10，运行10秒以上的语句被记录。   SHOW VARIABLES LIKE '%slow_query_log%'，查看慢查询是否开启，以及日志文件存储位置。   借助工具mysqldumpslow分析慢查询日志的一些常用方式：     假设慢查询日志地址为：/var/lib/mysql/hostname-slow.log

• 得到返回记录集最多的10个SQL
  • mysqldumpslow -s r -t 10 /var/lib/mysql/hostname-slow.log
• 得到访问次数最多的10个SQL
  • mysqldumpslow -s c -t 10 /var/lib/mysql/hostname-slow.log
• 得到按照实际排序的前10条里面含有左连接的查询语句
  • mysqldumpslow -s t -t 10 -g "left join" /var/lib/mysql/hostname-slow.log

  Explain（执行计划）

    Explain能帮助我们干什么：

• 表的去读顺序；
• 数据读取操作的操作类型；
• 哪些索引可以使用；
• 哪些索引被实际使用；
• 表之间的引用；
• 每张表有多少行被优化器查询；

    常用表字段说明：

• select_type:查询类型，用于区别普通查询、联合查询、子查询等复杂查询
• type:显示查询使用了哪种类型，从最好到最差一次排列
  • system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL 一般来说，得保证查询至少达到range级别，最好到达ref。
• rows:根据表统计信息及索引选用情况，大致估算找到所需的记录所需要读取的行数。
• extra:包含不适合在其他列中显示，但十分重要的额外信息。

标签：存储,查询,索引,详解,键值,数据,节点
From： https://www.cnblogs.com/Worth/p/16892042.html