【MySQL】索引

🍀一、什么是索引

MySQL 是索引的一种数据结构，他可以帮助数据库高校的查询、更新数据表中的数据。通过一定的排序规则排列数据表中的记录，加快对表的查询。索引一般是书籍、文献等，按照一定规则编排，方便查找特定内容的目录工具。例如，你在一个表格里面要查找自己的名字，你不同自己一行一行去看，直接在搜索栏里面搜索自己的名字。

🍀二、为什么要使用索引？

• 可以提高查询效率：减少数据库在执行查询需要扫描的数据量。在大量的数据中，如果没有索引需要扫描整个表，如果有了索引，那么可以快速定位。
• 实现数据库的唯一约束：通过创建唯一索引，可以确保表中某列或某组列的数据值具有唯一性。在“学生表”中，将“学生学号”列创建唯一索引，可以防止学号重复，确保数据的准确性和完整性。
• 支持数据的排序和分组操作：数据库在进行排序和分组操作时，如果相关列上有索引，数据库可以利用索引的有序性来高效完成这些操作，而无需额外的排序操作，从而提高查询性能。
• 优化连接操作：在多表连接查询时，索引可以帮助数据库更快的找到连接。

🍀三、索引的分类

🌺哈希索引

1. 结构特点：基于哈希表实现，通过索引键的哈希值直接定位数据位置，类似字典的“键-值”映射。
2. 优势：时间复杂度为O（1），查找速度快
3. 局限性：1.主要：不支持范围查找、排序和模糊查询；2.哈希冲突影响性能；3.MySQL并没有选择哈希作为默认数据结构，仅Memory默认支持。

🌺二叉搜索树

1.定义：二叉搜索树是一种特殊的二叉树，性质：

• 其左子树中所有节点的值均小于根节点的值；
• 其右子树中的所有节点的值均大于根节点的值；
• 左右子树本身也是二叉搜索树（递归定义）。

2.结构特点

• 每个节点最多有两个子节点（左孩子、右孩子）；
• 中序遍历得到的结果是有序递增的，便于快速查找

3.优势：

• 查找效率：理想情况下，插入、删除、查询时间复杂度为O（log2n）；
• 实现简单：逻辑简单，适合数量较小的场景。

4.局限性：

• 最坏情况下时间复杂度为O（n），BST退化为单链表时，时间复杂度为O（n）；
• 节点个数过多无法保证树高。磁盘效率低，磁盘IO是制约数据库性能的主要性能。
• 范围查询效率低，需要遍历多个节点。

🌺N叉树

1.定义：N叉树是每个节点最多有N个子节点（N>2）的树形结构，N的取值根据场景而定。

2.结构特点：

• 每个节点包含多个关键字和对应的子节点指针，关键字按顺序排序；

3. 优势：

• 降低树的深度：在相同数据量的情况下，可以有效控制树高，N越大，层级越少，大幅减少磁盘IO次数。
• 高效支持范围查询：时间复杂度为O（logN）。若子节点通过链表连接，可以快速扫描连续范围的数据。
• 适合大规模数据：节点可存储多个关键字。

4.局限性：

• N的取值需要合理设计；
• 节点结构更复杂。

🌳B树

1.定义：是一种平衡的多路搜索树，在B树中每个节点的子节点可以多于两个子节点。

2.查询方式：在B树查找一个关键字，从根节点开始，根据关键字与节点中关键字的比较结构决定进入哪个节点，知道找到关键字或者达到叶子结点为止。

如果想要画图可以点击下方链接来画图：

B—Tree

https://cs.csub.edu/~msarr/visualizations/BTree.html

🌳B+树

1.定义：B+是B树的一种变形，在B树的基础上进行优化，更适合在数据库中作为索引结构使用。经常用于数据库和文件系统等场合的平衡查找树。MySQL索引采用的数据结构。

2.查询方式：与B树类似，但是其可以利用叶子节点的链表结构，快速遍历范围内的所有数据。

如果想要画图可以点击下方链接来画图：

B+Tree

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B树和B+树是N叉树的具体实现。

🌳B+树与B树的区别