Mysql 索引
1. 索引介绍
一种用于快速查询和检索数据的数据结构，本质：一种排序好的数据结构
索引底层数据结构存在很多类型，常见的索引结构有：B树、B+树和 Hash、红黑树。在 Mysql 中，无论是 Innodb 还是 Myisam，都使用了 B+ 树作为索引结构
2. 优缺点
- 优点
- 加快 数据的检索速度
- 通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性
- 缺点
- 创建索引耗时，当 CUD 时，如果数据有索引，那么索引也需要动态修改，降低 SQL 执行效率
- 索引也需要物理存储，也会耗费一定空间
但是，使用索引一定能提高查询性能么?
- 大多数情况下，索引查询比全表查询要快
- 数据量不大时，提升不明显
3. 索引底层结构选型
Hash
不支持顺序和范围查询
二叉查找树 BST
非常依赖平衡程度
自平衡二叉查找树 AVL
AVL 树的特点：左右高度差不超过 1 ===> 查找、插入、删除复杂度都是 O(logn)
缺点；
- 频繁地进行旋转来操作来保持平衡
- 每个树节点仅存储一个数据，而每次进行磁盘 IO 时，只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘 IO
红黑树
B树 和 B+ 树
B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。
B 树& B+树两者有何异同呢？
- B 树的所有节点既存放键(key) 也存放数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
- B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
- B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
- 在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。
综上，B+树与 B 树相比，具备更少的 IO 次数、更稳定的查询效率和更适于范围查询这些优势。