数据结构与索引-- B+树索引

╰+哭是因爲堅強的太久メ 2023-01-13 01:55 205阅读 0赞

#### B+树索引 ####

*  上一节中我们讨论的都是B+树的数据结构的由来以及他的一些操作，B+树索引在本质就是B+树在数据库中的一个实现，但是B+索引在数据库中有一个特点就是他的高扇出性，因此在数据库中，B+树的高度一般是2~3层，也就是对于查找某一个键值的行记录，最多只需要2 ~ 3次IO，我们假设一般的磁盘每秒可以做100次IO，那么2 ~3次就差不多0.02 秒 ~0.03秒
    
     *  扇入数（引入）就是引入了多少别的模块引到自己模块来，像光线汇聚。
     *  扇出（输出）就是自己模块被多少个其他模块拿来使用，像瀑布铺洒。
     *  用如下图解释  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]
 *  数据库中的B+树索引分为聚集索引（clustered index）和辅助索引（secondary index），但是不管是聚集索引还是辅助索引，内部结构都是B+树，即高度平衡的，叶节点存放着所有的数据，***聚集索引与非聚集索引不同的是，叶子节点存放的是否是一整行的信息***

#### 聚集索引 ####

*  InnoDB存储引擎表是索引组织表，即表中数据依照主键顺序存放。而聚集索引就是按照每张表的主键构造一颗B+树，并且叶子节点存放整张表的行为记录数据，因此也让聚集索引的叶节点成为数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。和B+树数据结构一样，每一个数据页都通过一个双向链表来进行连接
 *  由于实际的数据页只能按照一颗B+树进行排序，因此每张表只拥有一个聚集索引。在许多情况下，查询优化器非常倾向于采用聚集索引，因此，聚集索引能够让我们在索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快的访问针对范围的查询。查询优化器能够快速发现某一段范围的数据页需要进一步扫描筛选数据。
 *  我们用如下的表以及数据来说明，我们以认为的方式让每一个页只能存放两个行为记录：

create table t(a int not null primary key, b varchar(8000))
    
    insert into t select 1, repeat('a', 7000);
    
    insert into t select 2, repeat('a', 7000);
    
    insert into t select 3, repeat('a', 7000);
    
    insert into t select 4, repeat('a', 7000);

*  我们如上表的定义，插入的数据使得目前每个页只能存放两个行记录，并且在构造的B+树上，数据页上存放的是完整的行记录，而在非数据页的索引页中，存放的仅仅是键值以及指向数据页的偏移量，而不是一个完整的行记录，因此我们构造这颗二叉树大致如下图:

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 1]

*  很多数据库文档中说过，聚集索引按照顺序物理的存储数据。如上图可以看到会有这种感觉。但是，如果聚集索引必须按照特定顺序存放物理记录的话，则维护成本会非常高。索引，聚集索引的存储并不是物理上连续的，相反，逻辑上才是连续的。有两点：
    
     *  一个是我们说过页面通过双向链表链接，页按照主键顺序排列
     *  每个页中的记录也是通过双向链表进行维护，物理存储上可以同样不按主键存储。
 *  聚集索引的一个好处是，他对于主键的排序查找和范围查找速度非常快。叶节点的数据就是我们要查询的数据，如果我们要查询一张注册用户的表，查询最后注册的10位用户，由于B+树索引是双向的，我们可以快速找到最后一个数据页，并去除10条记录，我们用explain分析如下：

EXPLAIN select * from moment order by id limit 10

![在这里插入图片描述][20210416104116109.png]

*  另一个是范围查找（range query），如果查找主键某个范围内的数据，通过叶节点的上层中间节点就可以得到页的范围，之后直接读取数据页即可，如下：

EXPLAIN select * from moment where id > 1590 and id < 20000

![在这里插入图片描述][20210416104306874.png]

*  上图中的rows代表是一个预估值，，如果实际查询这条sql的数据条数发现更多17384条。  
    ![在这里插入图片描述][20210416105326207.png]

#### 辅助索引 ####

*  对应辅助索引，也就是我们说的\*\*\*非聚集索引\*\*\*，叶节点不包含行的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark），该书签用来告诉InnoDB存储引擎，哪里可以找到与索引对应的行数据。因为InooDB存储引擎表是索引组织表，因此，InnoDB存储引擎的辅助索引的书签就是相应数据的聚集索引的键值。如下图表示InnoDB存储引擎中辅助索引与聚集索引的关系。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 2]
 *  辅助索引的存在并不影响数据在聚集索引中的组织关系，因此每张表可以有多个辅助索引，当通过辅助索引来查找数据时候，InnoDB存储引擎会遍历辅助索引并通过叶子节点上的指针获得指向主键索引的主键，让后通过主键索引再来找一次最终找到一个完整的记录。
 *  案例
    
     *  如果在一颗高度为3（根算0 层）的辅助索引中查找数据，那么需要对这可辅助索引遍历3次找到指定主键
     *  如果聚集索引树的的高度同样是3，那么还需要对聚集索引在进行三次查找，才能最终找到一个完整的行数据所在的页（InnoDB最小存储单元是页）
     *  因此一共需要6次逻辑IO来访问最终的一个数据页。
 *  此处也行会有疑问，为啥不直接将负责索引叶子上的 书签指针之间指向行数据所在的页呢，这样就可以和聚集索引一样，通过遍历一个B+树的索引就可以找到我们需要的数据页所在的位置，少了一次IO操作。
    
     *  的确在某些情况，例如只读的时候，书签是行标识的方式的非聚集索引 比 书签是主键方式的非聚集索引要快。
     *  但是这是考虑在OLTP（Online Transaction Processing， 在线事务处理）应用的情况下，表可能还需要提供其他服务，例如，insert，update，delete等DML操作。当进行这种操作时候，书签为行的标识符方式的非聚集索引可能就需要不断的更新行标识符所指向的数据页面的位置，这时候的开销可能就大于书签为主键的非聚集索引了
 *  又有另外一个疑问，那么DML操作也会影响主键索引，这个效率也会降低吗：
    
     *  DML操作的确会影响，但是主键是不能修改的，对于聚集索引来说 DML操作只会存在增加节点或者删除节点的情况，不会变更行的地址，而只是修改节点的指针数据而已
     *  B+树的节点操作我们在之前章节 [数据结构与算法–B树原理及实现][B] 中有过详细的解释。

#### B+树索引的管理 ####

*  索引的创建和删除通过两种方法，一种ALTER TABLE，一种CREATE/DROP index，具体预发略
 *  索引可以索引整个列的数据，也可以索引一个列的开头N行数据，例如建立前100 行的索引如下：

alter TABLE t add key idx_b(b(100));

*  MySQL数据库存在一个普遍问题，所有对所有的添加，删除操作，MySQL数据库都是先创建一个新的临时表，然后把数据导入临时表，删除原表，在吧临时表重命名为原来的表，因此对于一张大表，添加，删除索引非长久时间，
 *  InnoDB存储引擎从InnoDB Plugin开始，支持一种称为快速索引的创建方法，但是只限定于辅助索引，对于主键的创建和删除还是需要重建一张表。对于辅助索引的创建，InnoDB存储引擎会对表加上一个s锁。创建过程，不需要重建表，因此速度快，但是创建过程中上了S锁，因此创建过程中该表只进行读。
 *  删除的话更简单，只需要InnoDB存储引擎内部视图更新，将辅助索引空间标记可用即可，并删除MySQL内部视图上对改表索引定义。
 *  可用用如下方法查看索引：

show index from t

![在这里插入图片描述][20210416115120759.png]

*  上图中，有3个索引，一个主键索引，b列的非聚集索引，a,b的复合索引，如下图：  
    ![在这里插入图片描述][20210416155201229.png]
 *  具体每个列的含义：
    
     *  Table：索引所在表名
     *  Non\_unique：非唯一索引，可以看到primaryKey是0，因为必须是唯一索引
     *  Key\_name：索引名称，我们可以通过这个名称来DROP INDEX
     *  Sql\_in\_index：索引中该列的位置，如看到联合索引idx\_a\_b就比较直观的标识复合索引，位置有两个1,2
     *  Column\_name：索引列
     *  Collation：列以什么方式存储在索引中。可以上‘A’或者NULL。B+树总是A，即排序的。如果使用了Heap存储引擎，并且建立了Heap索引，这里就会显示NULL了，因为Hash根据Hash桶来存放索引数据，而不是对数据进行排序
     *  Cardinality：非常重要的值，表示索引中唯一值的数目的估计值。Cardinality表示的行数如果非常小，说明我们可能不需要这个索引，比如以上案例，只有四条数据，完全没有必要索引的。
     *  Sub\_part：是否是列的部分被索引。如果看idx\_b这个索引，这里显示100，表示我们只索引b列的前100个字符，如果索引整个列，该字段值是NULL
     *  Packed：关键字如何被压缩。如果没有被压缩，则为NULL
     *  Null：是否索引的列含义NULL值，可以看到idx\_b这里是yes，因为我们定义b列的时候允许NULL
     *  Index\_type：索引类型。InnoDB存储引擎只支持B+树索引，所以这里显示的都是BTREE
     *  Comment：注释
 *  其中Cardinality值比较关键，***查询优化器*** 会根据这个值来判断是否使用这个索引。但是这个值并不是实时更新，并非每次索引的更新都会更新改值，这样代价太大。因此这个值是不太准确的，只是一个估计值。上面显示的Cardinality为2，但是显然表中有四条数据，这个应该是4的。如果需要更新Cardinality信息，可以使用命令如下：

ANALYZE table t

*  不过这条命令在每个系统上可能得到的结果不一样，因为AnalyzeTable 现在还存在问题，可能会影响得到最后的结果，另一个问题是MySql对Cardinality计数的问题
 *  某些情况下可能会发生即使你建立了索引，但是查询这个字段确没有用到，或者，explain两条基本一样的语句，但是最终出来的结果一个用索引，一个不用索引，这个都和查询优化器对Cardinality的数量判断做的优化有关系。

[上一篇：数据结构与索引-- mysql InnoDB存储引擎索引][-- mysql InnoDB]  
[下一篇：数据结构与索引-- mySql索引诡异事件][-- mySql]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70]: /images/20221022/a32cd5414e54439b99fcd659d8205cff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 1]: /images/20221022/7008c486e1214a5f9b2cf06f5b5633a4.png
[20210416104116109.png]: /images/20221022/a32cb6e4395945758654d56c0137ac1d.png
[20210416104306874.png]: /images/20221022/87433a260e4541e59b6b8b478ffe0304.png
[20210416105326207.png]: /images/20221022/512e81586c004a5c886ebb24bee624c7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpYW9qaWFtaW4wMTAy_size_16_color_FFFFFF_t_70 2]: /images/20221022/d66f132836de4d08a820477136126bec.png
[B]: https://blog.csdn.net/liaojiamin0102/article/details/111375342
[20210416115120759.png]: /images/20221022/9eb8824b7b7e4d7788fd39b9b8d04454.png
[20210416155201229.png]: /images/20221022/c848d277d76e4b158563f9686211a5ae.png
[-- mysql InnoDB]: https://blog.csdn.net/liaojiamin0102/article/details/115719039
[-- mySql]: https://blog.csdn.net/liaojiamin0102/article/details/115861482