ChatGPT3.5使用体验( 三 ) _索引

B+ 树索引
B+ 树就是传统意义上的索引，这是目前关系型数据库中查找最为常用和最为有效的索引。B+ 树构造的索引类似于二叉树，根据键值快速 (Key Value) 快速找到数据。
有一点需要注意的是，B+ 树索引并不能找到给定键值具体的行。B+ 树索引能找到的只是被查找数据行所在的页。然后把页读入到内存中，再在内存中查找，找到查询的目标数据。
B+ 树是 B 树的变种，这里需要了解下 B 树。
为什么要引入 B 树或者 B+ 树呢？
红黑树等其它的数据结构也可以用来实现索引，为什么要使用 B 树或者 B+ 树，简单点讲就是为了减少磁盘的 I/O 。
一般来说，索引本身的数据量很大，全部放入到内存中是不太现实的，因此索引往往以索引文件的形式存储在磁盘中，磁盘 I/O 的消耗相比于内存中的读取还是大了很多的，在机械硬盘时代，从磁盘随机读一个数据块需要10 ms左右的寻址时间。
为了让一个查询尽量少地读磁盘，就需要减少树的高度，就不能使用二叉树，而是使用 N 叉树了，这样就能在遍历较少节点的情况下也就是较少 I/O 查询的情况下找到目标值。
比如一个二叉树，访问底部数据需要进行4次 I/O 操作。
如果使用4叉树，那么树的层架就会变矮，这时候只需要进行3次 I/O 操作。
数据量越来越大，N 叉树的效果更明显，在有相同数据的情况下，对于二叉树，能够大大缩小树的高度。
所以 B 树和 B+ 树就被慢慢演变而来了。
自平衡二叉树虽然能保持查询操作的时间复杂度在O(logn)，但是因为它本质上是一个二叉树，每个节点只能有 2 个子节点，那么当节点个数越多的时候，树的高度也会相应变高，这样就会增加磁盘的 I/O 次数，从而影响数据查询的效率。
为了解决降低树的高度的问题，后面就出来了 B 树，它不再限制一个节点就只能有 2 个子节点，而是允许 M 个子节点(M>2)，从而降低树的高度。
为什么 MySQL 用的是 B+ 树而不是 B 树呢，这里来看下区别？
B-tree和B+树最重要的区别是B+树只有叶子节点存储数据，其他节点用于索引，而B-tree对于每个索引节点都有Data字段。
B 树简单的讲就是一种多叉平衡查找树，它类似于普通的平衡二叉树。不同的是 B-tree 允许每个节点有更多的子节点，这样就能大大减少树的高度。
B-Tree 结构图中可以看到每个节点中不仅包含数据的 key 值，还有 data 值。而每一个页的存储空间是有限的，如果 data 数据较大时将会导致每个节点（即一个页）能存储的 key 的数量很小，当存储的数据量很大时同样会导致 B-Tree 的深度较大，增大查询时的磁盘 I/O 次数，进而影响查询效率。在 B+Tree 中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储 key 值信息，这样可以大大加大每个节点存储的 key 值数量，降低 B+Tree 的高度。
B+ 树相比与 B 树：
1、非叶子节点只存储索引信息；
2、所有叶子节点都有一个链指针，所以B+ 树可以进行范围查询；
3、数据都放在叶子节点中。
索引的分类
下面聊的索引，如果没有特殊说明，都是基于存储引擎来分析的。

文章插图
从物理角度可分为
1、聚簇索引（ index）；
2、非聚簇索引（non- index）。
聚簇索引（ index）
聚簇索引并不是一种单独的索引类型，而是一种数据存储的方式。在中聚簇索引实际上是在同一个结构中保存了 B+ 索引和数据行。
聚簇字面意思就是数据行和索引紧紧在一起的存储在一起。因为一个索引只能和一个数据存储在一起，所以一个表中只有一个聚簇索引。