目录

一、索引的概念、作用。

（1）介绍。

（2）为啥索引能优化sql查询？

1、某张表(emp)结构以及数据如下。

2、假如执行的SQL语句为：select * from emp where empno=7844;

3、对比与总结。

（3）索引特点。（表格）

（4）常见索引结构。

（5）索引小总结。

二、常见的数据结构。

（1）数组（线性表的一种）。

（2）链表。

（3）二叉搜索树。

（4）平衡二叉搜索树。

（5）红黑树。（也是二叉搜索树的一种）

（6）B树。（B-Tree）

（7）B+树。（更详细的下篇博客学习）

---

一、索引的概念、作用。

（1）介绍。

• 索引（index）是帮助MySQL高效获取数据的数据结构(有序的数据结构)。
• 在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据， 这样就可以在这些数据结构上实现高级查找算法，这种数据结构就是索引。
• 索引类似于书籍的目录，它允许数据库系统无需扫描整个表即可找到记录。

---

（2）为啥索引能优化sql查询？

1、某张表(emp)结构以及数据如下。

---

2、假如执行的SQL语句为：select * from emp where empno=7844;

• 普通表结构。无索引情况！

---

• 有索引情况！如果针对于这张表建立了索引。

• 且假设索引结构就是二叉树，那么也就意味着，会对empno这个字段建立一个二叉树的索引结构。（关于数据结构可以往下看！）

---

3、对比与总结。

• 当对指定字段（empno）添加了"二叉树"索引。此时我们在进行查询时，只需要扫描几次就可以找到数据了，极大的提高的查询的效率。
• 注意：这里我们只是假设索引的结构是二叉树，介绍一下索引的大概原理，只是一个示意图，并不是索引的真实结构。关于索引的真实结构，后面会详细介绍。

---

（3）索引特点。（表格）

• 使用索引的优势与劣势。

优势	劣势
提高数据检索的效率，降低数据库的IO成本。（因为没有索引，就会进行全表扫描，查询时一条一条比较次数就会很多，IO成本大）	索引列也是要占用空间的。索引需要单独利用空间存储。
通过索引列对数据进行排序，降低数据排序的成本，降低CPU的消耗。（例如mysql是B+树，是一个平衡多叉搜索树）	索引大大提高了查询效率。同时却也降低更新表的速度， 如对表进行INSERT、UPDATE、DELETE时，效率降低。

---

（4）常见索引结构。

• MySQL的索引是在存储引擎层实现的。
• 不同的存储引擎有不同的索引结构，主要包含以下几种。

索引结构	描述
B+Tree索引	最常见的索引类型，大部分引擎都支持 B+ 树索引
Hash索引	底层数据结构是用哈希表实现的, 只有精确匹配索引列的查询才有效, 不支持范围查询
R-tree(空间索引）	空间索引是MyISAM引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少。（经、纬度）
Full-text(全文索引)	是一种通过建立倒排索引,快速匹配文档的方式。类似于Lucene,Solr,ES

---

• 上述是MySQL中所支持的所有的索引结构。再来看看不同的存储引擎对于索引结构的支持情况。

• 注意： mysql中平常所说的索引，如果没有特别指明，都是指B+树结构组织的索引。

索引	InnoDB	MyISAM	Memory
B+tree索引	支持	支持	支持
Hash索引	不支持	不支持	支持
R-tree索引	不支持	支持	不支持
Full-text索引	5.6版本之后支持	支持	不支持

---

（5）索引小总结。

• 索引有关的作用——避免"慢sql"——>进行sql查询的优化。
• 索引是一种帮助MySQL高效获取数据的数据结构（如：数组、链表、二叉树、红黑树、b树、b+树、图...）

---

• 给表中的某一个列或多列——>加一个索引，就是给它加一种"数据结构"。
• 当需要根据这个数据去查询时，不是先去查询表，而是先根据这个数据的数据结构快速定位需要的数据。这样它的比较效率就高了——>查询效率变高。

---

• 但是当某个字段或多个字段添加了索引时，虽然查询效率增加，但它的增、删、改效率可能会降低。例如新增数据时，除了往表里增加数据，还要根据其数据结构添加其索引。删除数据时，还要删除其对应的索引。
• 所以当某张表的查询需求多，就增加索引。如果增、删、改需求多，就不推荐添加索引。

---

• MySQL如果不指明使用的索引——那就是B+树索引结构。
• MySQL的索引是在存储引擎层实现的。
• 不同的存储引擎对于索引结构的支持是不同的。

二、常见的数据结构。

• ArrayList、Linkedlist都是List接口的实现类。

（1）数组（线性表的一种）。

• ArrayList是一种常见的集合。
• 如ArrayList底层实现——长度可变的数组（线性表的一种）。
• 查询效率较快，但是增、删、改效率较低。

---

（2）链表。

• 如Linkedlist底层实现——链表（双向循环链表）。
• 查询效率较低、增删、改效率较高。

---

（3）二叉搜索树。

• 二叉搜索树（Binary Search Tree，BST）
• 进一步优化查询结构——二叉搜索树（左子节点<根<右子节点）

• 正常情况时的查询比较次数变少了。

• 若添加数据都是有序的，就会退化成链表了。查询的比较次数回到链表状态。

（4）平衡二叉搜索树。

• 继续优化——>无论怎么添加，都会自己通过旋转，保证左右子树的高度最多差1。
• 平衡二叉搜索树（Balanced Binary Search Tree，BBST）是一种特殊的二叉搜索树。
• 在保持二叉搜索树所有特性的同时，还保证了树的平衡性。平衡性是指树中任意两个叶子节点之间的最大深度差不超过1。这种平衡性确保了树的操作（如查找、插入、删除）都能在对数时间复杂度内完成，即O(log n)。

• 缺点是各个子节点的移动旋转较为消耗资源。

（5）红黑树。（也是二叉搜索树的一种）

• 继续优化。各个节点变成红色或黑色。
• 平衡变成——>到任意一个节点所经过的黑色节点个数平衡。

---

• 主要通过旋转和变色进行平衡。但是相较于普通的平衡二叉搜索树消耗资源更少。

• 红黑树仍然是一个二叉搜索树，即对于任意节点，其左子树中的所有节点的值都小于该节点的值，其右子树中的所有节点的值都大于该节点的值。

• 红黑树需要满足以下性质。
• <1>每个节点要么是红色，要么是黑色。
• <2>根节点是黑色。
• <3>每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
• <4>从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

---

• 问题如下。随着元素的大量增多，如何降低树的高度？？

• 如果随着元素的增多，那么树的高度也会增加。因为2的n（n:树的高度）次方-1=当前树高最多能拥有的元素。太高的树，且子节点只有两个，则当数据量大时，缺陷又体现出来了。如果将一个树的根节点能拥有子节点扩大数量，那么就可以"压缩"树了。

• 所以又产生了"B树"与"B+树"。

（6）B树。（B-Tree）

• B树（B-Tree）是一种自平衡的树数据结构，它能够保持数据有序，并且允许进行搜索、顺序访问、插入和删除操作。
• B树特别适用于存储在存储介质（如硬盘）上的数据集合，因为它可以减少磁盘I/O操作的次数。
• 在插入和删除操作中，B树可能会进行节点的分裂和合并以保持树的平衡。
• 当插入一个新键值时，如果节点未满，直接插入。如果节点已满，则节点分裂，并将中间的键值提升到父节点。

---

• B-Tree，B树是一种多叉路平衡查找树。
• 相对于二叉树，B树每个节点可以有多个分支，即多叉。
• 以一颗最大度数（max-degree）为5(5阶)的b-tree为例，那这个B树每个节点最多存储4个key（值），5 个指针。如下。

• 5阶代表5个指针。也就是根节点上的4个key(值)左右的5个指针。

• 还是一样的左边比根节点小，右边比根节点大。

---

• 举例4阶B树。（根节点4个指针、3个key(值)）
• 当元素添加不足4个时，不会分裂。

• 满足4个元素时。中间大小的元素往上。
• 这样就让树的高度就被"压缩"了。

（7）B+树。（更详细的下篇博客学习）

• B+Tree是B-Tree的变种，我们以一颗最大度数（max-degree）为4（4阶）的b+tree为例，来看一下其结构示意图。

• 蓝色框框起来的部分，是索引部分，仅仅起到索引数据的作用，不存储数据。

• 红色框框起来的部分，是数据存储部分，在其叶子节点中要存储具体的数据。

---

与普通的B树相比较，主要有三种区别：

• 所有的数据都会出现在叶子节点。

• 叶子节点形成一个单向链表。

• 非叶子节点仅仅起到索引数据作用，具体的数据都是在叶子节点存放的。