欢迎 👍点赞 ➕关注 ❤️收藏 💬评论
目录
🍀一、什么是索引
MySQL 是索引的一种数据结构，他可以帮助数据库高校的查询、更新数据表中的数据。通过一定的排序规则排列数据表中的记录，加快对表的查询。索引一般是书籍、文献等，按照一定规则编排，方便查找特定内容的目录工具。例如，你在一个表格里面要查找自己的名字，你不同自己一行一行去看，直接在搜索栏里面搜索自己的名字。
🍀二、为什么要使用索引？
- 可以提高查询效率：减少数据库在执行查询需要扫描的数据量。在大量的数据中，如果没有索引需要扫描整个表，如果有了索引，那么可以快速定位。
- 实现数据库的唯一约束：通过创建唯一索引，可以确保表中某列或某组列的数据值具有唯一性。在“学生表”中，将“学生学号”列创建唯一索引，可以防止学号重复，确保数据的准确性和完整性。
- 支持数据的排序和分组操作：数据库在进行排序和分组操作时，如果相关列上有索引，数据库可以利用索引的有序性来高效完成这些操作，而无需额外的排序操作，从而提高查询性能。
- 优化连接操作：在多表连接查询时，索引可以帮助数据库更快的找到连接。
🍀三、索引的分类
🌺哈希索引
- 结构特点：基于哈希表实现，通过索引键的哈希值直接定位数据位置，类似字典的“键-值”映射。
- 优势：时间复杂度为O（1），查找速度快
- 局限性：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+Treehttps://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
B树和B+树是N叉树的具体实现。
🌳B+树与B树的区别
| 区别 | B树 | B+树 |
| 节点存储 | 叶子节点、非叶子节点存储索引+数据 | 非叶子节点进存储索引，叶子节点存储索引+数据 |
| 查询路径 | 数据分布在所有节点，可以在非叶子节点找到所查询的数据 | 非叶子节点的值都保存在叶子节点，数据只分布在叶子节点，非叶子节点值保存对子节点的应用，没有保存真实数据。只能在叶子节点找到所查询的数据 |
| 范围查询 | 逐层遍历节点 | 叶子节点使用双链表连接，叶子节点之间有一个相互连接的引用，可以通过子节点找到兄弟节点 |
