深入理解Mysql底层数据结构和算法

什么是索引

索引是帮助MySQL高效获取数据的排好序的数据结构

数据结构有哪些

数据结构模拟网站：Data Structure Visualization

• 二叉树

不适合做自增ID的数据结构。如下示意图，假设采用二叉树作为表自增主键ID的数据存储结果如下：当查询id为5的数据时，其查询次数为5次

• 红黑树

不适合做mysql的索引，因为当表数据太大时，树的高度也同时增大，导致高度不可控和查询速度同时变慢。

• Hash表

1. 对索引的key进行一次hash计算就可以定位出数据存储的位置
2. 很多时候Hash索引要比B+ 树索引更高效
3. 仅能满足 “=”，“IN”，不支持范围查询
4. hash冲突问题

• B-tree

每个节点都会保存data数据。

• B+tree

Mysql存储结构和索引结构

1、存储结构

InnoDB存储引擎的逻辑存储结构和 Oracle大致相同 ，所有数据都被逻辑地存放在一个空间中 ，我们称之为表空间 （ tablespace ） 。表空间又由段 （ segment ） 、区 （ extent ） 、页 ( page ） 组成，InnoDB存储引擎的逻辑存储结构大致如图所示。

段（segment）

段是表空间文件中的主要组织结构，它是一个逻辑概念，用来管理物理文件，是构成索引、表、回滚段的基本元素。上图中显示了表空间是由各个段组成的，常见的段有数据段、索引段、回滚段等。InnoDB存储引擎表是索引组织的（index organized），因此数据即索引，索引即数据。那么数据段即为B+树的叶子节点（上图的leaf node segment），索引段即为B+树的非叶子节点（上图的non-leaf node segment）。

创建一个索引（B+树）时会同时创建两个段，分别是非叶子节点段和叶子节点段.。在索引数据量一直增长的过程中，所有新的存储空间的申请，都是从“段”这个概念中申请的。

区（extents）

innodb里的段（segment）又由多个区组成，在代码中被称为extent，区是由64个连续的页（page）组成的，每个页大小为16KB，即每个区的大小为1MB。一个区是物理上连续分配的一个段空间，每一个段至少会有一个区，在创建一个段时会创建一个默认的区。如果存储数据时，一个区已经不足以放下更多的数据，此时需要从这个段中分配一个新的区来存放新的数据。一个段所管理的空间大小是无限的，可以一直扩展下去，但是扩展的最小单位就是区。

页（page）

InnoDB有页（page）的概念，可以理解为区的细化，页是InnoDB磁盘管理的最小单位。

常见的页类型有：

1. 数据页（B-tree Node）。
2. Undo页（Undo Log Page）。
3. 系统页（System Page）。
4. 事务数据页（Transaction system Page）。
5. 插入缓冲位图页（Insert Buffer Bitmap）。
6. 插入缓冲空闲列表页（Insert Buffer Free List）。
7. 未压缩的二进制大对象页（Uncompressed BLOB Page）。
8. 压缩的二进制大对象页（Compressed BLOB Page）。

在逻辑上（页面号都是从小到大连续的）及物理上都是连续的。在向表中插入数据时，如果一个页面已经被写完，系统会从当前区中分配一个新的空闲页面处理使用，如果当前区中的64个页都被分配完，系统会从当前页面所在段中分配一个新的区，然后再从这个区中分配一个新的页面来使用；

索引结构B+树

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构。B-Tree结构中每个节点不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大增加每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：

（1）非叶子节点只存储关键字信息

（2）所有叶子节点之间都有一个双向链表指针

（3）数据记录都存放在叶子节点中

为什么使用B+Tree?

MySQL是基于磁盘的数据库系统,索引往往以索引文件的形式存储的磁盘上,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取，I/O存取的消耗要高几个数量级（每次存取都是按页来操作的）,所以要尽量减少索引树的高度。

（1）B+树的一个节点刚好也是一页。

（2）B+树索引节点不存储数据，因此一个索引节点可以存储更多的索引节点，每个节点能索引的范围更大更精确，也意味着 B+树单次磁盘IO的信息量大于其它树状结构，I/O效率更高。

（3）B+树的数据全部存储在叶子节点，而叶子节点是双向链表，可以很高效的实现区间查询。

库表文件存储位置

Mysql存储引擎

存储引擎是作用到表上的，不同存储引擎的存储内容不一样，同样的是都采用B+tree的索引结构（Mysql做了优化在叶子节点采用了双链表）。如下图示意中InnoDB与MyISAM存储引擎表对应的存储文件区别。

InnoDB:

•InnoDB索引文件和数据文件是一体的(聚集)

frm：存储表结构信息

ibd：存储索引和数据

主键索引

1、表数据文件本身就是按B+Tree组织的一个索引结构文件
2、聚集索引-叶节点包含了完整的数据记录

• 为什么建议InnoDB表必须建主键，并且推荐使用整型的自增主键？ 

建主键的目的是让存储引擎可以采用主键创建索引。如果没指定主键则系统会找表里边数据都不相同的列创建索引，如果表里边没有数据都不相同的列则创建一个隐藏列并维护1个rowid。

建议采用整形作为主键，是因为整形好做比较和排序且占用空间小。有的表可能采用UUID作为主键，UUID 虽然可以用字符的ASCII码进行比较，但是比较耗时间（比如比较两个UUID需要一位一位的比较）且长度比较大。

自增有利于顺畅的插入元素。如果不是自增的，则在插入新元素时可能发生树平衡和重构。

非主键索引

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

(一致性和节省存储空间)

联合索引

联合索引需要遵循最左匹配原则。如果没有按照最左匹配则会导致查询不走索引。原理就如上图，假如查询条件没有name只有age和position字段查询条件，则会导致无法按照索引的排序去查找数据只能查全表。

从 MySQL 5.1 版本开始，MySQL 就开始支持将 B+ 树索引的所有非叶子节点放在内存中的优化方式，这被称为 InnoDB 的“主内存散列索引”（main memory hash index）或者简称为“散列索引”（hash index）。在这种优化方式下，非叶子节点不再使用 B+ 树结构存储，而是使用更高效的散列结构进行组织。

这种索引优化方式最早是在 InnoDB 存储引擎中引入的，然后逐渐得到了优化和改进。从MySQL 5.5版本开始，InnoDB 引入了更强大的“InnoDB Buffer Pool”（即内存缓冲池），并且支持将索引的数据和非叶子节点全部放入内存中，从而极大地提高了查询性能。

需要注意的是，虽然主内存散列索引可以显著提高查询性能，但它也需要消耗更多的内存资源。因此，在使用这种优化方式时，需要确保服务器具备足够的内存容量以容纳索引数据和非叶子节点。

MyISAM：

frm：存储表结构信息

MYD：存储表数据信息

MYI：存储表索引信息