深入理解MySql索引底层数据结构与算法

淡淡的烟草味﹌ 2022-01-26 14:47 357阅读 0赞

索引是排序号的数据结构  
索引是用来优化数据库查询速度的，是表级别的。  
mysql会根据主键来自动建立索引方便查询。  
下面介绍索引的底层原理以及很多细节的步骤。

## 1. 为什么使用B+树而不使用二叉搜索树或者红黑树 ##

二叉搜索树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
红黑树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]  
B树：  
![在这里插入图片描述][20190529111227888.png]  
首先二叉搜索树是不能够自己调整高度的。  
红黑树能够自己调整高度，用在java的HashMap中，但是红黑树也是二叉树，建立索引之后的高度仍然太高。  
而B-树和B+树每一层能够存储更多的节点。

--------------------

### 2. B树和B+树的区别 ###

B树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 2]  
B+树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 3]  
**B树和B+树主要有两点区别：**

1.  B+树的非叶子节点不存储data，，只存储key这样，可以增大长度。因为cpu读取磁盘到内存中的时候，是按照页来进行读取的，一页为4K，一般最多也就读取三四页的样子，因此不存储data可以多读取索引值，减少I/O次数，加快查询。
2.  B+树叶子节点有顺序访问指针，可以加快访问的性能，主要可以加快范围查找的性能，比如查找age>20的，就可以通过指针直接查找，如果使用B树，还要返回到上一层来查找

--------------------

### 3. 两种索引原理(MyISAM和InnoDb) ###

两者都是表级别的索引，在建立表的时候，可以自行选择。

#### 区别一：聚集索引和非聚集索引 ####

MyISAM是非聚集的，也就是说索引文件和数据文件是分离的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 4]  
在MyISAMB+树中，key是主键，value是数据存放的磁盘地址，根据主键查找地址，然后再根据地址来查找数据。

但是在InnoDb中，是聚集索引，也就是说叶子节点的value是完整的数据记录，根据key可以直接查找到所有的数据。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 5]

#### 区别二：非主键索引 ####

MyISAM在查找非主键的时候，与主键一样建立索引：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 6]

InnoDb不一样。非主键索引的叶子节点存储的是主键的值  
因为这样**可以保证数据的一致性和节省存储空间**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 7]

#### 区别三：存储文件 ####

MyISAM表在磁盘上有三个文件：  
![在这里插入图片描述][20190529112435412.png]  
frm是表数据结构，MYD是表数据，MYI是表索引。  
也就是MyISAM根据表索引MYI来查找表数据MYD

而InnoDB只有两个存储文件，idb文件存储的是索引+数据  
![在这里插入图片描述][20190529112532178.png]

--------------------

### 4. 一次I/O读取页的大小 ###

通过这个查询sql可以看到B+树的页大小  
![在这里插入图片描述][20190529113539932.png]  
![在这里插入图片描述][20190529113610655.png]  
可以看到结果为16K，16K个字节  
**为什么mysql页文件默认16KB？**  
假设一行数据大小为1K，那么一页能够存16条数据，也就是一个叶子节点能够存16条数据  
假设主键ID为byte类型，那么长度为8B(字节)，指针大小在InnoDb与源码中为6B，因此一共14B，那么一页可以存：  
16K/14=1170个(主键+指针)  
那么一颗高度为2的B+树能够存储的数据为：1170x16=18720条，  
一颗高度为3的B+树能够存储数据为：1170x1170x16=21902400(千万级)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 8]

这也显示了为什么用B+树而不使用B树的原因：  
B+树的数据是不存储在非叶子节点上的，这也非叶子节点可以存放更多的索引数据，使得树的高度更小，优化了查询速度，同时B+树还有范围查询快，数据查询开销平均等优点。

B+树的高度一般也就5行一下，也就是几次磁盘I/O就能够查询出。

--------------------

### 4. InnoDB为什么必须有索引 ###

InnoDB表必须有主键，并且推荐使用整型的自增主键。如果自己不建立主键，InnoDB会自己选择一个默认的列做索引。

--------------------

### 5. 自增整型和uuid作为主键的选择 ###

整型的索引占8个字节，uuid占的字节数更多，因此不推荐使用uuid作为主键索引。  
另外uuid不合适进行比较，uuid需要先转换为ASCII码  
因此加快查询速度可以使用整型索引，优点很多。  
另外为什么选择自增？  
如果插入了小于之前索引的元素，可能会造成分裂。这样会降低性能。

--------------------

### 6. 联合索引 ###

B+树的联合索引的底层存储结构长什么样？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 9]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220126/1280d7841fdd45c9ba2ba835fb520d83.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]: /images/20220126/d874ed2b44724c0bb850e5ab5e098940.png
[20190529111227888.png]: /images/20220126/785a1d8f01cd4a4788d4c01f0f811a30.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 2]: /images/20220126/4db4d66a81694b839ee0acc0f7044dd2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 3]: /images/20220126/dc555bad86a54669abbaafe5796c6d97.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 4]: /images/20220126/ce74e49ebb5247439438319b80741a93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 5]: /images/20220126/48eee0ba7411404eb4961cf1ca47143a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 6]: /images/20220126/010e05c66d8b416196c2d13037ac681b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 7]: /images/20220126/0ad097c7ed57444a97da4bffd40637ed.png
[20190529112435412.png]: /images/20220126/27f9eeedba974ebe90654b292387f0c0.png
[20190529112532178.png]: /images/20220126/7b75f607fa4b41a8b90e4eb4f5a7df72.png
[20190529113539932.png]: /images/20220126/f2acc162b8e84930a12d472ae2009b0a.png
[20190529113610655.png]: /images/20220126/70352599ab4741769bab44d3013fd615.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 8]: /images/20220126/f21d04ef40264815948f22d530bbc07b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 9]: /images/20220126/600e2559fcfb4f828e00e96894bd5eb4.png