MySQL相关：索引数据模型推演及 B+Tree 的详细介绍( 四 ) _索引数据

文章插图

基于以上规则，可以推导出：

从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的 2 倍。

为什么不用红黑树？

只有两路；不够平衡。红黑树一般只放在内存里面用。例如 JAVA 的 TreeMap 。

索引方式：真的是用的 B+Tree 吗？在 Navicat 的工具中，创建索引，索引方式有两种，Hash 和 B Tree 。
HASH：以 KV 的形式检索数据，也就是说，它会根据索引字段生成哈希码和指针，指针指向数据。

文章插图

哈希索引有什么特点呢？

它的时间复杂度是 O(1)，查询速度比较快。因为哈希索引里面的数据不是按顺序存储的，所以不能用于排序。我们在查询数据的时候要根据键值计算哈希码，所以它只能支持等值查询（= IN），不支持范围查询（> < >= <= between and）。另外一个就是如果字段重复值很多的时候，会出现大量的哈希冲突（采用拉链法解决），效率会降低。

问题： InnoDB 可以在客户端创建一个索引，使用哈希索引吗？

我们先到官网看看介绍： dev.mysql.com/doc/refman/… InnoDB utilizes hash indexes internally for its Adaptive Hash Index feature 直接翻译过来就是：InnoDB 内部使用哈希索引来实现自适应哈希索引特性。这句话的意思是 InnoDB 只支持显式创建 B+Tree 索引，对于一些热点数据页，InnoDB 会自动建立自适应 Hash 索引，也就是在 B+Tree 索引基础上建立 Hash 索引，这个过程对于客户端是不可控制的，隐式的。我们在 Navicat 工具里面选择索引方法是哈希，但是它创建的还是 B+Tree 索引，这个不是我们可以手动控制的。在 buffer pool 里面有一块区域是 Adaptive Hash Index 自适应哈希索引，就是指这个。

这个开关默认是 ON：
show variables like 'innodb_adaptive_hash_index';复制代码从存储引擎的运行信息中可以看到：
show engine innodb statusG复制代码

----------------------BUFFER POOL AND MEMORY-----------------------------------------------------------INSERT BUFFER AND ADAPTIVE HASH INDEX-------------------------------------复制代码

因为 B Tree 和 B+Tree 的特性，它们广泛地用在文件系统和数据库中，例如windows 的 HPFS 文件系统，Oracel、MySQL、SQLServer 数据库。
B+Tree落地形式MySQL 架构通过上节课我们知道，MySQL 是一个支持插件式存储引擎的数据库。在 MySQL 里面，每个表在创建的时候都可以指定它所使用的存储引擎。
这里我们主要关注一下最常用的两个存储引擎，MyISAM 和 InnoDB 的索引的实现。
MySQL 数据存储文件首先，MySQL 的数据都是文件的形式存放在磁盘中的，我们可以找到这个数据目录的地址。在 MySQL 中有这么一个参数，我们来看一下：
show VARIABLES LIKE 'datadir';复制代码每个数据库有一个目录，我们新建了一个叫做 checkit 的数据库，那么这里就有一个checkit 的文件夹。
这个数据库里面我们又建了 5 张表：archive、innodb、memory、myisam、csv 。
我们进入 checkit 的目录，发现这里面有一些跟我们创建的表名对应的文件。
在这里我们能看到，每张 InnoDB 的表有两个文件（.frm 和.ibd），MyISAM 的表有三个文件（.frm、.MYD、.MYI）。

文章插图

有一个是相同的文件，.frm 。

.frm 是 MySQL 里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成。
我们主要看一下其他两个文件是怎么实现 MySQL 不同的存储引擎的索引的。
在 MyISAM 里面，另外有两个文件：
一个是.MYD 文件，D 代表 Data，是 MyISAM 的数据文件，存放数据记录，比如我们的 user_myisam 表的所有的表数据。
一个是.MYI 文件，I 代表 Index，是 MyISAM 的索引文件，存放索引，比如我们在 id 字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面。
也就是说，在 MyISAM 里面，索引和数据是两个独立的文件。
那我们怎么根据索引找到数据呢？
MyISAM 的 B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI 中找到键值后，会到数据文件.MYD 中获取相应的数据记录。