mysql数据结构

Mysql数据表中的数据在磁盘中分布位置可能是不连续的，在读取数据时，每读取一条数据就进行一次磁盘IO效率是很低的，为了减少IO次数，索引就诞生了，通过索引，我们可以快速定位到数据位置，增加查询效率，索引是一种排好序的数据结构。

索引的几种数据结构:

二叉树

如下图所示：二叉树会把数据分成两组，值小的数据放左边，大的放右边，同样是找89，如果用链表的方式查，需要查6次，而二叉树只需要查两次，极大的提升了效率。

但Mysql底层没有采用这种数据结构，比如Col1的值是顺序增长的，这种单边增长的值在二叉树中和链表没有什么区别，也是去做顺序查找，对查询效率没什么帮助。

红黑树

又叫自平衡二叉树，它会自动优化二叉树的结构，下图中，二叉树查询需要6次，红黑树只要3次，但是数据量大的时候，它的树的高度会很高，从根节点查询到叶子结点也会经历多次IO，效率也很慢，所以也不是Mysql的数据结构。

B-Tree

也不是Mysql的数据结构， 这种数据结构中，会在一个大的数据节点里存储很多小的索引元素，使每次IO可以把一批索引加载到内存中，提升查询效率，其中data存储的是索引所在行的磁盘文件地址（K-V结构），节点中的数据索引按照从左到右递增排列。

B+Tree

Mysql底层使用这种数据结构，可以说是对B-Tree的优化，节点中的索引也是从左到右递增排列，data数据都存储在叶子节点，多个叶子节点组成一个磁盘页，叶子节点之间通过指针链接Mysql中把B+Tree优化成了双向指针，指针存储相邻磁盘页的地址。非叶子节点只存储索引，并且节点中的每一个元素值就是它指向的下一层节点的磁盘页的第一个值。在构建B+Tree的时候，每个磁盘页的第一个元素会存储在非叶子索引中，通过二分查找法，可以快速定位数据行在磁盘中的地址。

Mysql中一个节点的大小为16kb，例如一个索引类型是bigint，占8字节，加上下一个磁盘的文件地址6字节是14字节，一个非叶子节点就可以放1170个元素。叶子节点不太一样，因为存储引擎不同，data在Innodb中存储整行数据信息，在Mylsam中存储磁盘地址信息，如果是Innodb，每行1kb也能存储16个元素。假设树的高度为三，一个B+Tree能存储的数据量就是：1170 X 1170 X 16 大概2200万，得出结论就是，同样的数据量情况下，每个节点中能存储的索引元素越多，树的高度就会越小，查询效率就越快。

B-Tree和B+Tree的区别

Mylsam

Mylsam索引文件和数据文件是分离的

对应三个文件：frm：存储表结构信息、MYD：存储数据行、MYI：存储索引

使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

查询一条数据的时候，如果查询条件增加了索引，会先从MYI文件中找到对应行的索引信息，在通过索引中data的磁盘地址值去MYD文件查询数据。

Innodb

Innodb表数据文件本身就是按B+Tree组织的一个索引结构文件 对应两个文件：frm：存储表结构信息、ibd：存储索引及数据行 该存储引擎会把表数据直接存储到叶子节点的data里 Innodb的主键索引就是聚集索引，Mylsam是非聚集索引

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

为什么建主键

Innodb表创建的时候一定会用B+Treel来组织一个索引结构，主键是自带主键索引的，所以说建了主键的话会直接用主键来组织索引结构。如果不建主键，它会从表中选择一列所有元素都不相等的列，把这个列来当成组织B+Tree的数据列，如果没有这样的列，Mysql会自动建一个隐藏列用来组织索引结构。

为什么用整型

如果使用不是整型的UUID做主键，在查询阶段会用AscII码去比对大小，效率就会降低，整型的主键对比大小就会快很多，并且整形占用空间也比较小，尤其数据量大时可以节约磁盘空间。

为什么用自增

如果使用非自增的UUID做主键，在插入新数据时，因为叶子节点是顺序排列的，如果不是有序的值，就会导致节点分裂，分裂还可能导致树做自平衡。但如果使用自增主键，每次插入都是往后增加新节点，就不会出现这些情况，效率会提高很多。

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

主要是为了节约存储空间，因为主键的叶子节点已经存储了数据，所以就没必要再存储数据。

非主键索引是非聚集索引，这样设计的缺点是非主键索引找到叶子节点的主键值后，会做回表操作（重新回到聚集索引中找到真正的数据行）。

联合索引的底层数据结构长什么样

先比较id，如果id相等，再比较name，如果name也相等，则再比较date。（索引最左前缀原理）