[高阶数据结构八] B+树和索引原理深度解析

1.前言

B树并不常用,就是因为有B+树的存在. MySQL的索引底层其实就是使用了B+树,但是B+树和索引都是在了解了B树之后才深度学习的，如果你对于B树海一无所知的话，请阅读下面这篇文章。

[高阶数据结构三] B-树详解_b-树csdn-CSDN博客

本章重点：

本章着重讲解B+树与B树的区别，以及mysql中相关索引的原理。

2.B+树的原理

B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：

1. 分支节点的子树指针与关键字个数相同
2. 分支节点的子树指针p[i]指向关键字值大小在[k[i]，k[i+1])区间之间
3. 所有叶子节点增加一个链接指针链接在一起
4. 所有关键字及其映射数据都在叶子节点出现

B+树所有的非叶子节点都是不存储数据的，只有在叶子节点上面才会存储数据。所以在B+树中的查找时，只有找到叶子节点上面，才能够找到数据，非叶子节点是不可能获得数据的。

B+树的插入和删除这里就不过多的进行赘述，想了解的可自行查找资料。

3.B*树的原理

B*树和B+树一样，只有在叶子节点才可能命中数据，而对于B*树来说，由于增加了兄弟之间的指针连接，那么当进行范围的查找数据时，可以不用反复的从根节点出发查找，而是直接在兄弟节点通过指针来进行遍历访问。这样可以减少IO的次数

通过学习B树，B+树，B*树

4.索引的原理

B- 树最常见的应用就是用来做索引 。索引通俗的说就是为了方便用户快速找到所寻之物，比如： 书籍目录可以让读者快速找到相关信息，hao123 网页导航网站，为了让用户能够快速的找到有价 值的分类网站，本质上就是互联网页面中的索引结构。

当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数 据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法， 该数据结构就是索引。

MySQL里面有两种索引：Innodb和MyiSAM索引。

MyISAM引擎: B+树

注意：MyiSAM索引在这里面叶子节点存储的并不是数据，而是数据所在磁盘中的地址，如果需要访问数据，还需要拿着这个地址再进行一次IO去磁盘中访问数据。

 上面使用的是主键索引，如果还需要除了主键索引以外的其他索引，那么在MyiSAM这个搜索引擎上面也是可以的。

例如：以col2做一个普通索引

普通索引存储的也是数据在磁盘中的地址，然后想要访问数据也是根据地址再进行一次IO，去磁盘中寻找数据。

---

总结：

InnoDB 存储引擎支持事务 ，其设计目标主要面向在线事务处理的应用，从 MySQL 数据库 5.5.8 版 本开始， InnoDB 存储引擎是默认的存储引擎 。 InnoDB 支持 B+ 树索引、全文索引、哈希索引。但 InnoDB使用 B+Tree 作为索引结构时，具体实现方式却与 MyISAM 截然不同。

当使用主键索引时，数据和KEY值是没有分离的，当找到了KEY值，那么就可以直接读取数据，而在MyISAM中，找到了KEY值，还需要进行一次IO。

这种数据和KEY值不分离的索引也可以称之为聚簇索引。

如果需要使用普通索引的话，那么普通索引的叶子节点存储的是普通索引在表中对应的主键索引的值。

例：

结论：在InNoDB中，除了主键索引的叶子节点是存储数据的以外，其他任何索引（普通索引，唯一键索引等）叶子节点存储的都是主键索引的值，想通过普通索引来找到数据，那么就需要先找到主键索引，然后再根据主键索引，查找到对应的值。

那肯定有人就有疑问了，那如果我自己没有设置主键索引呢，只设置了普通索引该怎么办呢？

因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有 主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数 据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，那么普通索引的叶子节点对应的主键就是自动生成的这个主键。

---

总结：在InNoDB中，只有主键索引中的叶子节点才会存储数据，其他的索引的叶子节点根本不存储数据，叶子节点存储的是主键索引的值。当使用Innodb做索引值时，需要多次进行磁盘的IO才能够找到真正的数据。

5.总结

对于索引这一块并没有阐述的非常细致，因为我们这毕竟是在阐述数据结构，并不牵涉数据库，如果对于索引，事物这一块感兴趣，可以后续自行查找资料学习MYSQL。

高阶数据结构写到这就全部讲解完毕了，希望对大家能有所帮助。

原文地址：https://blog.csdn.net/weixin_62196764/article/details/144256860

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！