mysql底层数据结构

mysql索引是为了快速查找数据而把数据按照一定规则排列的数据结构

查看数据结构地址：Data Structure Visualization

一、索引数据结构分类

1、无索引查找

普通的查找就是通过全表扫描，数据存储在磁盘上的位置是随机的，所以查找耗时

2、二叉树查找

二叉树都有一个规律，就是根节点比左边元素大，比右边元素小；如果是以自增int类型的索引字段，1为根节点，往下都是右子节点，这和没建索引是一样的

3、红黑树查找

红黑树的数据排列相对二叉树来说就会稍微好一点，它会根据插入数据做平衡，但是在实际生产环境下，数据量越大树的高度就越高，系统数据日积月累，数据的查询就会越来越慢

4、b树查找

在红黑树的基础上做横向扩张，这样就可以相对降低树的高度，每个节点存储多个元素，元素存储的结构使key、value形式，叶子节点不包含所有数据，查询的次数虽然减少了，但是每个元素都存有数据，每次查询都需要加载到内存中定位到，有点耗费内存，查询速度也不是那么理想

在mysql上存储的是每个元素都存有数据，如图

5、b+树查找

和b树一样，从左到右都是有顺序的，b+树数据结构如下图：

非叶子不存储数据，叶子节点包含所有数据；另外每个叶子节点之间是有指针的

6 hash

mysql经过内部的hash运算得到存储位置，找到查询的结果，但是有个问题，如果是范围查询就和索引失效没什么区别了

7、为什么mysql选择b+树而不选择b树

mysql中可以查找Innodb每次加载树节点最大容量

show global status like 'Innodb_page_size';

具体原因有以下几点：

1. b树每次查询加载根节点的容量是有限制的，也就是说b树存放元素比b+树存储的元素要少，树的高度也就越高，IO次数越多，查询越慢
2. 如果是范围查询，b+树的叶子节点之间有指针指向下一个叶子节点，而b树没有，b+树查询到结果可以返回，而b树把根节点加载到内存，一直循环往下找到结果，由于没有指针指向，又要重新从根节点开始加载

二、MyISAM和InnoDB

 建了两个表对应的存储引擎分别是InnoDB和MyISAM，gaorufeng_innodb.ibd文件存储的表结构、数据和索引；gaorufeng_myisam.MYD存的是数据，gaorufeng_myisam.MYI存的是索引，gaorufeng_myisam_12633.sdi存的是表结构。由此可见MyISAM索引树存储的索引对应数据的所在地址，找到地址后在去MYD文件中找到整条数据

 找到地址后就可以找到数据行，MyISAM存储引擎的主键索引其实可以理解为非聚簇索引，InnoDB的主键索引是聚簇索引

三、索引的分类

1、聚簇索引

2、非聚簇索引

3、联合主键索引

 

4、联合非主键索引

5、最左前缀原理

假设有一个表table，有一个联合索引，联合索引字段包含a，b，c

select * from table where a = '1' and b = '2' and c = '3'
select * from table where b = '2' and c = '3'
select * from table where c = '3'

肯定是第一条sql语句联合索引生效，因为跳过前面的字段，其它后面都是无序

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

1. 如果不建主键，mysql在构建索引树时会从一列中选取不重复数据的列构建b+树，如果没有不重复数据的列，mysql会自己新建一个隐藏列，类似rowid，有点耗费性能
2. 如果不用整型，像uuid，内部肯定是用ascii码做排序，另一个就是存储空间比整型要大
3. 为什么要自增，假如b+树节点最大元素容量是3，当超过3个就分裂形成子元素，这时候有一个节点是3，4，9，插入一个5，如果是自增的话只要新增一个节点存储就行，现在插入导致节点分裂，树还要做一下平衡，效率比较低

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

1. 节省空间，如果还存储其它数据，数据量大的话索引占用空间大
2. 维护索引树方便，因为如果不管什么索引树的叶子节点都存储整张表数据，那肯定要先保证所有索引树的叶子节点都插成功才行；所以像我们这种只维护主键索引树的叶子节点就行，等主键索引插成功再把id维护到非主键索引树的叶子节点上

到此这篇关于mysql底层数据结构的文章就介绍到这了,更多相关mysql请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文地址：https://blog.csdn.net/gp3056/article/details/131185244