一文让你对mysql索引底层实现明明白白

公众号新闻

2024-01-23 11:01

作者：京东云开发者-京东零售韩航云

链接：https://my.oschina.net/u/4090830/blog/10139889

一、索引到底是什么

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

. 索引是存储在文件里的

. 数据结构：二叉树 HASH BTREE

如果没有索引的话，循环一条一条的找，找一次就是一次 IO，这样速度就会很慢

我们知道数据库数据都是存在磁盘上的，当我们查找数据时，就会从磁盘上取数据，每取一次就是一次 IO，IO 是非常耗时的，为了速度快会把数据放到缓存里，然后在缓存里进行操作

二、磁盘存取原理

当查找数据的时候，就是磁头循环找此道，就会一直循环查找，一次查找就是一次 IO，IO 是很耗时的

三、Mysql 数据结构详解

就拿上面的 7 条数据来说，如果没有索引，当我们查找第 7 条数据时，就会循环 7 次，如果有百万级别的数据，那么就会查找百万次，显然这样是不行的，就需要数据结构算法来优化，那我们就从二叉树 ----HASH---BTREE 来一一说起

二叉树：

二叉树节点保存的都是单个索引，高度会随着数据增大而增高，但是比一条一条的循环会快

不用二叉树是因为的极端情况下会出现单边增长，这样在数量大的情况下，和一条一条查找没有区别。

红黑树：

红黑树有自平衡性质，不会出现单边增长，它会动态自旋转，在性能上比二叉树又高一点，但是 mysql 也没有用这种数据结构，因为数据量超大的情况下，数据高度也会一直增大，在最终这个树高度也非常大，解决不了根本问题

HASH:

hash 算法一次就会定位到文件指针，速度快，但是还是没有用，如果范围查找的话就没有办法了，如果只是内存中的话，他的时间复杂度是 O (1), 速度会会很快，但是索引文件也是保存在磁盘上，而且 hash 是不连续的放在磁盘上的，这样查询起来也很慢，这才是不用 hash 的最根本原因

B-TREE:

相比上面的数据结构，b-tree 增加了横向大小（度 Degree），那么在高度上就减小了，查找次数就少了

15，56，77.。。。。是索引，data 就是对应的一行数据

那么在横向的度上最大多少合适呢？？总不能横向上一直扩展下呀，磁盘一次 IO，就是取一个横向的节点（度），把一个节点的数据放在缓存中，那么一次 IO 也不能把所用的数据全取出来，所以最好是一次 io，就把这个节点全取处理，电脑操作系统从磁盘一次取数据到内存中一般是 4K，而 mysql 取一次数据一般是 16K，所以横向节点一般设置为 **16K。** 因为一个节点设置成 16K 的话，这个节点保存了索引和索引对应行的数据，那么这个节点横向保存不了太多的数据，所以，这种数据结构也不合适，引入新的数据结构