文章目录

• • （1）索引认识
  • • 1. 认识
    • 2. 二叉树
    • 3. 红黑树
    • 4. 数据库索引为什么要用 B+ 树而不用红黑树呢？
    • 5. B-Tree
    • 6. B+树
    • 7. B+树和B树区分
  • （2）B+树索引结构

（1）索引认识

1. 认识

索引是提升查询速度的一种数据结构。

索引之所以能提升查询速度，在于它在插入时对数据进行了排序（显而易见，它的缺点是影响插入或者更新的性能）。

所以，索引是一门排序的艺术，有效地设计并创建索引，会提升数据库系统的整体性能。在目前的 MySQL 8.0 版本中，InnoDB 存储引擎支持的索引有 B+ 树索引、全文索引、R 树索引。

下面的网站可以动态的观察各类数据结构的原理
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

2. 二叉树

如果以二叉树构建索引结构的话，那么select * from table where col1=6需要查找6次.尤其对于这种原先数据有序的条件下，二叉树的右子树会不断扩大，查找的次数也是线性增长的

3. 红黑树

1：根节点为黑色
2：每个叶子节点都是黑色的节点，叶子节点不存储数据
3：任何相邻的节点都不能同时为黑色，也就是说红色节点是被黑色结点隔开的
4：每个结点，从该结点到达其可到达叶子节点所有路径，都包含相同数量的黑色结点（较长的路径由于红黑相间，而由于是不大于二倍所以黑色的结点数量是相同的）

如果通过红黑树构建索引的话，查询数据6需要查询3次.

4. 数据库索引为什么要用 B+ 树而不用红黑树呢？

AVL 树和红黑树这些二叉树结构的数据结构可以达到最高的查询效率这是毋庸置疑的.
既然如此，那么数据库索引为什么不用 AVL 树或者红黑树呢？
这就牵扯到一个问题了，不考虑每种数据结构的前提条件而选择数据结构都是在耍流氓.
AVL 数和红黑树基本都是存储在内存中才会使用的数据结构，那磁盘中会有什么不同呢？
这就要牵扯到磁盘的存储原理了
操作系统读写磁盘的基本单位是扇区，而文件系统的基本单位是簇(Cluster).
也就是说，磁盘读写有一个最少内容的限制，即使我们只需要这个簇上的一个字节的内容，我们也要含着泪把一整个簇上的内容读完.
那么，现在问题就来了
一个父节点只有 2 个子节点，并不能填满一个簇上的所有内容啊？那多余的内容岂不是要浪费了？我们怎么才能把浪费的这部分内容利用起来呢？哈哈，答案就是 B+ 树.
由于 B+ 树分支比二叉树更多，所以相同数量的内容，B+ 树的深度更浅，深度代表什么？代表磁盘 io 次数啊！数据库设计的时候 B+ 树有多少个分支都是按照磁盘一个簇上最多能放多少节点设计的啊！
所以，涉及到磁盘上查询的数据结构，一般都用 B+ 树啦.

5. B-Tree

1：叶子节点具有相同的深度，叶子节点的指针为空
2：所有索引元素不重复
3：节点中的数据索引从左到右递增排列

6. B+树

1：非叶子节点不存储data，只存储索引（冗余），可以放更多的索引
2：叶子节点包含所有索引字段
3：叶子节点用指针连接，提高区间访问的性能

之所以选择B树而非红黑树是因为通过B树可以控制树的高度，减少磁盘IO次数，MySQL的数据和索引都是存储在磁盘上的.此外每个节点可以增加存储的索引元素个数，充分利用每个簇(Cluster)能够得到有效使用

7. B+树和B树区分

1：B+树叶子节点增加了相邻指针
2：B+树非叶子节点只存储了key，没有存储data数据
3：B+树非叶子节点存储的是冗余元素，这样做能够让非叶子节点存储更多的key索引

（2）B+树索引结构

B+ 树索引是数据库系统中最为常见的一种索引数据结构，几乎所有的关系型数据库都支持它。

那为什么关系型数据库都热衷支持 B+树索引呢？因为它是目前为止排序最有效率的数据结构。像二叉树，哈希索引、红黑树、SkipList，在海量数据基于磁盘存储效率方面远不如 B+ 树索引高效。

所以，上述的数据结构一般仅用于内存对象，基于磁盘的数据排序与存储，最有效的依然是 B+ 树索引。

B+树索引的特点是： 基于磁盘的平衡树，但树非常矮，通常为 3~4 层，能存放千万到上亿的排序数据。树矮意味着访问效率高，从千万或上亿数据里查询一条数据，只用 3、4 次 I/O。

又因为现在的固态硬盘每秒能执行至少 10000 次 I/O ，所以查询一条数据，哪怕全部在磁盘上，也只需要 0.003 ~ 0.004 秒。另外，因为 B+ 树矮，在做排序时，也只需要比较 3~4 次就能定位数据需要插入的位置，排序效率非常不错。

B+ 树索引由根节点（root node）、中间节点（non leaf node）、叶子节点（leaf node）组成，其中叶子节点存放所有排序后的数据。当然也存在一种比较特殊的情况，比如高度为 1 的B+ 树索引：

上图中，第一个列就是 B+ 树索引排序的列，你可以理解它是表 User 中的列 id，类型为 8 字节的 BIGINT，所以列 userId 就是索引键（key），类似下表：

CREATE TABLE User (
  id BIGINT AUTO_INCREMENT PRIMARY KEY,
  name VARCHAR(128) NOT NULL,
  sex CHAR(6) NOT NULL,
  registerDate DATETIME NOT NULL,
  ...
)

所有 B+ 树都是从高度为 1 的树开始，然后根据数据的插入，慢慢增加树的高度。你要牢记：索引是对记录进行排序， 高度为 1 的 B+ 树索引中，存放的记录都已经排序好了，若要在一个叶子节点内再进行查询，只进行二叉查找，就能快速定位数据。

可随着插入 B+ 树索引的记录变多，1个页（16K）无法存放这么多数据，所以会发生 B+ 树的分裂，B+ 树的高度变为 2，当 B+ 树的高度大于等于 2 时，根节点和中间节点存放的是索引键对，由（索引键、指针）组成。

索引键就是排序的列，而指针是指向下一层的地址，在 MySQL 的 InnoDB 存储引擎中占用 6 个字节。下图显示了 B+ 树高度为 2 时，B+ 树索引的样子：

可以看到，在上面的B+树索引中，若要查询索引键值为 5 的记录，则首先查找根节点，查到键值对（20，地址），这表示小于 20 的记录在地址指向的下一层叶子节点中。接着根据下一层地址就可以找到最左边的叶子节点，在叶子节点中根据二叉查找就能找到索引键值为 5 的记录。

那一个高度为 2 的 B+ 树索引，理论上最多能存放多少行记录呢?

在 MySQL InnoDB 存储引擎中，一个页的大小为 16K，在上面的表 User 中，键值 userId 是BIGINT 类型，则：

说明：可以通过下面的命令查看页大小
SHOW GLOBAL STATUS LIKE ‘Innodb_page_size’

根节点能最多存放以下多个键值对=16384 / 键值对大小（8+6）≈ 1170

其中键值对中8表示索引主键userId 因为是BIGINT 所以占8个字节，其中6表示的指针即指向下一层的地址的占用大小

再假设表 User 中，每条记录的大小为 500 字节，则：

叶子节点能存放的最多记录为 = 16K / 每条记录大小 ≈ 32

综上所述，树高度为 2 的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1170 * 32 =  37440

这个就可以大约看到B+树高度为2时，就可以存在37440条数据。

同理，树高度为 3 的 B+ 树索引，最多能存放的记录数为：

总记录数 = 1170（根节点） * 1170 （中间节点） * 32 =  43804800

高度为 3 的 B+ 树索引大约可以存在4300万的数据，那么如果高度为4的话，可以存储几十亿的数据，这在绝大部分场景下都是可以涵盖的。