共计 3729 个字符，预计需要花费 10 分钟才能阅读完成。
本篇内容主要讲解“mysql 索引内部实现与算法分析”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让丸趣 TV 小编来带大家学习“mysql 索引内部实现与算法分析”吧!
存储引擎从索引的根节点开始进行搜索，通过节点槽中的指针向下层查找，比较节点页的值和要查找的值找到合适的指针进入下层子节点。存储引擎最终要么找到对应的值，要么该记录不存在。
叶子节点的指针指向的是被索引的数据，而不是其他的节点页
索引可以按值查找之外，还可以用于查询中的 order by 操作(原因：索引树中的节点是有序的)
B+tree 索引的限制：
1. 如果不是按照索引的最左列开始查找，则无法使用索引
2. 不能跳过索引中的列
3. 如果查询中有某个列的范围查找，则其右边所有列都无法使用索引优化查找
B+ 树的插入操作
B+ 树的插入必须保证插入后叶节点中的记录依然排序，
插入 B + 树的三种情况
第一种情况，往图中插入 28，leaf page 和 index page 都没有满，直接插入
第二种情况，往图中插入 70，leaf page 满了，index page 没有满
说明：采用旋转操作使得其减少一次页的拆分操作
第三种情况，在图中插入 95，leaf page 和 index page 都满了
说明：B+ 树为了保持平衡，对新插入的键值可能需要大量的拆分页操作，但是 B + 树主要用于磁盘，我们应该尽可能减少页的拆分，可以通过旋转功能（leaf page 已经满了，但是左右兄弟节点没有满）
B+ 树的删除操作
B+ 树使用填充因子来控制树的删除变化，50% 是填充因子可设的最小资。同样必须保证删除后叶节点中的记录依然排序。
删除 B + 树（根据填充因子的变化来衡量）的三种情况
在图中删除 70
在图中删除 25，此时 25 的兄弟节点的 28 更新到 page index 中
在图中删除 60，此时填充因子小于 50%，需要做合并操作
B+ 树索引
B+ 树索引本质是在 B + 树在数据库中的实现 特点：扇出性
数据库中 B + 树索引分为：聚集索引（clustered index）、辅助聚集索引（secondary index）
索引组织表：表中数据按照主键顺序存放
堆表：按照插入数据顺序存放，堆表上的索引都是非聚集的，且堆表没有主键
聚集索引(每张表只有一个): 按照每张表的主键构造一棵 B + 树，且叶节点存放着整张表的行记录数据，所以聚集索引的叶节点也成了数据页，
辅助聚集索引的叶节点上存放的仅仅是键值以及指向数据页的偏移量，不是一个完整行记录
聚集索引不是一种单独的索引类型，而是一种数据存储方式。innodb 的聚集索引实际上在同一个结构中保存了 B +tree 索引和数据行。
当表有聚集索引时，数据行实际上是存储在索引的叶子页中
说明：聚集索引的存储在物理上是不连续的，在逻辑上是连续的：1. 页通过双向链表链接，页按照主键的顺序排序；2. 每个页中的记录也是通过双向链表进行维护，物理存储上可以同样不按照主键存储
聚集索引的优点：
可以把相关数据保存在一起
数据访问更快(聚集索引将索引和数据保存在同一个 b +tree 中)
使用覆盖索引扫描的查询可以直接使用页节点中的主键值
聚集索引的缺点：
聚集数据提高了 IO 性能，如果数据全部放在内存中，则访问的顺序就没那么重要了
插入速度严重依赖插入顺序。按主键的顺序插入是速度最快的。但如果不是按照主键顺序加载数据，则需在加载完成后最好使用 optimize table 重新组织一下表
更新聚集索引列的代价很高。因为会强制 innod 将每个被更新的行移动到新的位置
基于聚集索引的表在插入新行，或主键被更新导致需要移动行的时候，可能面临页分裂的问题。页分裂会导致表占用更多的磁盘空间。
聚集索引可能导致全表扫描变慢，尤其是行比较稀疏，或由于页分裂导致数据存储不连续的时
非聚集索引比想象的更大，因为二级索引的叶子节点包含了引用行的主键列
非聚集索引访问需要两次索引查找(非聚集索引中叶子节点保存的行指针指向的是行的主键值)，对于 innodb 自适应哈希索引可以减少这样的重复工作
辅助索引：叶节点包含键值，且每个叶级别的索引行还包含一个书签（相应行数据的聚集索引）
辅助索引和聚集索引的关系图
说明：辅助索引的存在不影响数据在聚集索引中的组织，所以每张表可以有多个辅助索引
原理：通过辅助索引来寻找数据时过程：innodb 会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。
B+ 树索引的管理
索引的创建和删除的方法：alter table；create /drop index
创建主键索引过程：先创建一张新的临时表，然后将数据导入临时表，删除原表，再把临时表重名为原来的表名
创建辅助索引过程：在创建过程中不需要重建表，只会对表加上一个 S 锁，速度极快。
通过 show index from table_name 可以查看表中索引的信息
说明：
table：索引所在的表名
Non_unique: 非唯一索引，primary key 是 0
Key_name: 索引的名称
Seq_in_index: 索引中该列的位置
Column_name：索引的列
Collation: 列以什么方式存储在索引中，B+ 树索引总是 A，即排序；如果使用了 heap 存储引擎，且建立了 hash 索引，就会显示 NULL，因为 hash 通过 hash 桶来存放索引数据，而不是对数据进行排序
Cardinality: 表示索引中唯一值的数目的估计值，Cardinality/ 表的行数 尽可能接近 1，太小则需要重建该索引
Sub_part: 是否是列的部分被索引，如只索引某一列的前多少字符，如果索引整个列，则该字段为 NULL
packed：关键字如何被压缩。没有被压缩则为 NULL
NULL：是否索引的列含有 null 值，
Index_type: 索引的类型，innodb 只支持 B + 索引
comment: 注释
B+ 树索引的使用
当访问高选择性字段并从表中取出很少一部分行时，就需要对这个字段添加 B + 树索引
注：当取出数据量超过表中数据的 20%，优化器就不会使用索引，而是进行全表的扫表。且预估的返回行数的值是不准确的
顺序读、随机读、预读取
顺序读（sequntial read）：顺序地读取磁盘上的块（block）
随机读（random read）：访问的块不是连续的，需要磁盘的磁头不断移动
预读取（read ahead）：通过一次 IO 请求将多个页预读取到缓冲池中
随机预读取（random read ahead）：当一个区（64 个连续页）中 13 个页也在缓冲区中，并在 LRU 列表的前端（即页是被频繁访问），则 innodb 会将这个区剩余的所有页预读到缓冲区
线性预读取（linear read ahead）：基于缓冲池中页的模式，而不是数量。如果一个区中的 24 个页都被顺序访问了，则 innodb 会读取下一个区的所有页
innodb_read_ahead_threshold 参数：表示一个区中的多少页被顺序访问时，innodb 才启用预读取。默认值为 56，即当一个区中的 56 个页被顺序访问时，则预读取下个区的所有页
联合索引：还是一棵 B + 树，不同的是联合索引的键值的数量不是 1，而是大于等于 2
哈希算法
自适应哈希索引使用的是散列表（hash table）的数据结构
哈希表（散列表）：由直接寻址表改进而来
哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效
原理：对每一行数据，存储引擎会对所有的索引列计算一个哈希码(很小且不同键值的行计算出的哈希码也不一样)，哈希索引将所有哈希码存储在索引中，同时也保存着每个数据行的指针。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中
在 mysql 中，只有 memory 引擎显示支持哈希索引(注：为非唯一哈希索引)，NDB 支持唯一哈希索引，innodb 支持自适应哈希索引
哈希索引的限制：
1. 哈希索引只包含哈希值和行指针，而不存储字段值，索引不能使用索引的值来避免读取行
2. 哈希索引数据并不是按照索引值顺序存储的，所以无法用于排序
3. 哈希索引不支持部分索引匹配查找(因为哈希索引始终是使用索引列的全部内容来计算哈希值的)
4. 哈希索引只支持等值查询，包括 =，in
5. 当出现哈希冲突 (不同的索引列值却有相同的哈希值) 时，存储引擎必须遍历链表中所有的行指针，逐个比较直至找到符合条件的行
6. 如果哈希冲突很多，则索引维护操作的代价会很高（要避免哈希冲突，必须在 where 条件中带入哈希值和对应列值）。
自适应哈希索引
通过 Innodb_adaptive_hash_index 参数可以开启自适应哈希索引，数据库启动时会自动创建槽数为 innodb_buffer_pool_size/256 个哈希表
可以通过 show engine innodb status 查看当前自适应哈希索引的使用状况
说明：包括哈希索引的大小，使用情况，每秒使用自适应哈希索引搜索的情况
注：哈希索引只能用来搜索等值的查询，其他类型不能使用哈希索引
到此，相信大家对“mysql 索引内部实现与算法分析”有了更深的了解，不妨来实际操作一番吧！这里是丸趣 TV 网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
