MySQL索引背后的内部结构示例详解_Mysql

索引的认识：

索引是数据库中的一个数据结构，用于加速查询操作。

作用：

数据库中的表、数据、索引之间的关系，类似于书架上的图书、书籍内容和书籍目录的关系。
索引所起的作用类似书籍目录，可用于快速定位、检索数据。
索引对于提高数据库的性能有很大的帮助

比如一本字典，如果一一的查找，这个效率将会很低下。

但如果给它加上标签的话，就一下可以找到你想搜索的东西，所有它大大提高了我们的查询速度。

索引可以提高查询速度，但可能会拖慢增删改的速度，后续对数据进行增删改的操作，都是要同步索引的。但在实际开发中，查询的频率要远远高于增删改的操作，所以这是利大于弊

索引的使用：

//查看索引
show index from 表名;
//创建索引
//对于非主键、非唯一约束、非外键的字段，可以创建普通索引
create index 索引名 on 表名(字段名);
//删除索引
drop index 索引名 on 表名;

操作：

注意:

索引的创建也是一个危险操作！！！
针对空表或者数据量比较小的表中创建索引没有任何问题，但如果表中数据很大，此时创建索引将会引起大量的cpu/硬盘io的消耗，可能会把mysql直接搞挂；

解法方法：

1.预测哪个索引可能会频繁使用，根据建议，提前给它创建好
2.引入新的数据库服务器，提取创建好索引，将旧的数据库服务器数据慢慢导入到新服务器中（常规做法）；

索引底层的数据结构：

索引一定是引入了一些额外的数据结构，加快了查询速度！

引入索引的目的，就是通过其他的数据结构，来加快查询的速度，以便减小表的遍历！

那么哪些数据结构可以加快查询速度？

1.顺序表：随机访问，并且插入删除效率低下不适合加快查询速度

2.链表：从头依次遍历，更不能加快查询速度

3.哈希表

哈希表

众所周知，哈希表查询速度是最快的，构造出合适的哈希函数，可以达到o(1)查询速度,即使在极端情况下，将所有值通过哈希函数映射到一个同哈希桶上，达到o(n)，这种情况一般只存在于理论上，现实中几乎不可能出现。最坏情况下，设置哈希桶上的每个链表长度为m，o(m)也是近视o(1)。

虽然哈希表的查询速度特别快，但是它只能查找特定的某个值（key），并不是一连串的范围，但数据库中一般要我们查找的情况下是一系列的范围数据，所以并不适合数据库查询；

4.树

二叉搜索树的数据中序遍历是连续范围的数据是有序的，可以进行范围查询，如果是一个比较平衡的二叉树搜索树遍历速度o(logn) 最坏情况下变成一个链表，就会变成o(n)速度

avl树

是一颗严格的二叉搜索树，左右子树高度不能超过1 所以遍历速度o(logn) 但是当你非常严格的情况下，每次进行增删改的操作，从而触发旋转操作，每次旋转，都会有开销。

红黑树

而红黑树并没有avl树那么严格，触发旋转的概率很小，虽然没有avl树平衡，但是查询速度也没差多少

红黑树里面的数据中序遍历是连续范围的数据是有序的，可以进行范围查询，但由于它是二叉类型的，如果数据量特别大，这会让树的高度变得非常高，树的高度每加一层，比较次数就会增加一次，由于数据都是保存在硬盘中，就会多要一次硬盘io操作了，它查询的效率就会变得慢，所以并不适合大规模的数据

因此就引入了b树，它是一个n叉搜索树，同样数量的数据，需要的节点变少了，树的高度大大降低了，从而减小了遍历的次数。

b树：

以上是b树的大概形状

1.每个节点上的key是有序的，比较的时候可以直接用二分查找

2.b树会控制每个节点上的key的数量，如果key太多，就会分裂更多的叶子节点出来

3.多个数据，都是放在一块连续的存储空间上，比较的时候，使用一次io就可以遍历完整个节点因此b树更适合对应这种数据量的范围查找，但数据库索引的最终形态是b+树，b树的升级版

b+树：

b+树也是n叉树对比b树 b+树做了进一步优化

1.b+树每个父节点的元素都会在子节点的最大值出现

2. b树的每个节点都包含键值（key）和相应的值（value）（包括叶子节点和非叶子节点）。而b+树非叶子节点只存储键值（key）也就是id，叶子节点存储所有的数据，并且每个叶子节点是以链表结构存储起来的，b+树可以通过简单的顺序访问叶子节点来高效地执行范围查询。

3.进行每次查询操作，都会落到最终的叶子节点上，每次经历的硬盘io次数都是稳定的（稳定做一件事在计算机中很重要）

4. b+树的非叶子节点都存储的数据比较小，所有可以存储在内存中，进一步减小硬盘io的次数

特性	b树	b+树
数据存储位置	数据存储在所有节点（包括内部节点）	数据只存储在叶子节点
内部节点	存储键和值	仅存储键（不存储数据）
叶子节点链接	无链接	叶子节点通过链表连接
查询效率	适合单点查询	更适合范围查询
范围查询性能	较差	非常高效（通过叶子节点链表）
树的高度	相对较高	较低
内存/磁盘利用	内存和磁盘利用相对较低	更高效，能容纳更多节点

mysql中支持多种存储引擎，其中innodb最常用（也是面试做常考查的内容），不同的存储引擎使用的索引也是不同的

b+树搜索：

下面来介绍b+树在有无索引的情况下如何检索：

create table employees (
    id int primary key,
    name varchar(50),
    age int
);

在这张表中，id为主键，所有默认会创建索引，name和age列则没创建索引

1）遍历有主键索引的列

select * from employees where id = 5;

mysql 会利用 b+ 树索引，直接从根节点开始查找，快速定位到 id = 5 的叶子节点，查询的时间复杂度为 o(log n)。

2）遍历无索引的列

select * from employees where name = 'zhangsan' ;

mysql 只能通过全表扫描来查找数据，效率较低，尤其在表的数据量较大时。

3）遍历有索引的列却不是主键索引

create index index_id on employees(age) ;

此时为age列创建索引

select * from employees where age = 20 ;

此时根据关于age的b+树找到对应叶子节点，但此时非主键索引的b+树的叶子节点存储的都是主键id，因此找到id之后，再在id主键索引的b+树中遍历找到对应的叶子节点，此时叶子节点才正在存储我们想要找到的数据；

因此需要遍历俩次b+树，第一次找到主键id，再在主键id的b+树找到对应的值；

总结：

没有索引的情况下，mysql 只能通过全表扫描来查找数据，效率较低，尤其在表的数据量较大时。
使用 b+ 树索引的情况下，mysql 可以通过 b+ 树的查找机制（o(log n) 的复杂度）高效地定位记录，从而大大提升查询性能。b+ 树支持点查询和范围查询，尤其对于大数据量的表，具有非常重要的优化作用。

到此这篇关于mysql索引背后的内部结构的文章就介绍到这了,更多相关mysql索引结构内容请搜索代码网以前的文章或继续浏览下面的相关文章希望大家以后多多支持代码网！