MYSQL索引的由来及实现原理

短命女 2023-10-17 18:38 28阅读 0赞

##### 索引的概念 #####

*  索引是帮助高效获取数据的一种数据结构。
 *  索引是也可能是一种文件。（对于数据库来说是一种文件，但是索引在其他方面的应用有可能不是文件）

##### 索引的引入 #####

**1.磁盘的一点概念**  
  因为我们操作数据库查询数据，其实也是要到硬盘上读取文件，那么先引入硬盘的几个概念：`柱面`、`磁道`、`扇区` 。  
  如下图所示，是我们磁盘中的一个磁片的俯视图：  
![这里写图片描述][70]  
  再加一张关于柱面的：  
![这里写图片描述][70 1]

通过观察以上两张图，这里暂时只需要知道，我们的数据的大概存储的方式，即，这三个来锁定数据在磁盘上的位置，即通过`柱面` ——> `磁道` ——> `扇区` 来找到数据。

**2.数据查询的步骤**  
  对于数据库中的查询，比如下表(U\_USER)

<table> 
 <thead> 
  <tr> 
   <th>ID</th> 
   <th>NAME</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>1</td> 
   <td>James</td> 
  </tr> 
  <tr> 
   <td>2</td> 
   <td>mic</td> 
  </tr> 
  <tr> 
   <td>3</td> 
   <td>tom</td> 
  </tr> 
 </tbody> 
</table>

现在，如果我们有这样的查询需求：

select * from u_user where id = 1;

体现在磁盘上的话，就会去到上图中的扇区里从开始位置按顺序查找返回。但是如果我们有这样的查询，即查询`3` 这条数据:

select * from u_user where id = 3;

同样体现在磁盘上的话，也是找到那个扇区，然后还是从开始位置按顺序依次在扇区中查找，直到找到`3` 这条数据（如下图所示）。但是这样的话，就会影响到我们的查询速度，因为每次都要从开始位置依次查找。  
![这里写图片描述][70 2]  
  假如我们提前知道`3` 这条数据在磁盘上的物理位置，我们就可以根据地址直接锁定到这条数据，获取出来，这样的话就大大提高了我们的查询速度，**这也就是索引概念的由来**。这样数据查询的过程，就会变成下图的过程：  
![这里写图片描述][70 3]  
  当然，真正在操作系统上，还会有`缓存` 的概念，如下：  
`时间局部性原理` ：意思是说，对于查询完`3` 数据后，系统会考虑到我们可能在`一定` 时间内再次查询，它会把该数据在一段时间内缓存起来。  
`空间局部性原理` ：对于扇区中的数据，当我们在读取`3` 这条数据，系统会考虑到当前扇区`3` 这条数据一定范围内的数据，可能会被我们下次查到，它就会缓存起来这一部分数据。  
   通过以上的功能，也来提高我们的查询效率。

**3.mysql数据库中的数据文件**  
  一种是，如果我们的mysql使用的存储引擎是`MyISAM` ，在你的数据存储文件中关于以上表的存储就会是下边三个：

u_user.frm  //该文件存储的是，当前表的信息，比如字段类型等等
    u_user.MYD  //该文件存储的是，数据
    u_user.MYI  //该文件存储的是，索引

在查询时，首先找到这个索引文件，然后再根据地址查找到数据。

另外一种，如果我们的mysql使用的存储引擎是`InnoDB` ，其实默认也是这个`InnoDB`存储引擎，在你的数据存储文件中关于以上表的存储可能会是下边这两个：

u_user.frm  //该文件存储的是，当前表的信息，比如字段类型等等
    u_user.idb  //该文件存储的是，带有索引的数据（索引和数据是在一起的）

工作的原理也大概如此，但是不一样的，我理解的是，对于`MyISAM` 引擎，索引文件里存储的是`索引字段` 和 `数据的地址` ，但是对于`InnoDB` 引擎来说，它的`idb` 文件里，是`索引字段` 和 `整条数据记录` ，`innoDB` 中的索引是表级别的。  
  这里其实我有一个疑问，难道不管数据记录多大，都会是`索引字段` 和 `整条数据记录` ？如果建立多个`索引字段` ，那结构又会变成什么样？

**4.mysql数据库索引的数据结构选择**  
  既然方法有了，那怎么才能更快的建立索引，按照索引查询出数据，即，需要设计一个合理的数据结构，来提高效率。  
  mysql使用的数据结构，是通过`B+Tree` 来实现，它与其他的`binary Tree` 、`Red/Black Tree` 相比来说，`B+Tree` 的优点是，建立起来的数据结构的高度可以是**恒定的**,而数据就存储在最下边的`叶子上` ，而每次查找一个索引的时候，需要的时间，需要的步骤都是`相同的` ,即如下图所示，数据存储在最下边，每次找到索引数字的次数，都是需要两步，这样速度上，相对其他的结构是最好的。  
![这里写图片描述][70 4]

##### 声明原创，以上学习来自，咕泡学院的James老师讲的一节公开课 #####

[70]: https://img-blog.csdn.net/20180309200344838?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd29oYXFpeWk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180309200516382?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd29oYXFpeWk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 2]: https://img-blog.csdn.net/20180309210038413?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd29oYXFpeWk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: https://img-blog.csdn.net/20180309210021691?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd29oYXFpeWk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 4]: https://img-blog.csdn.net/2018030921515036?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd29oYXFpeWk=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70