文章目录
- 1. 什么是索引？
- 2. 索引的优缺点
- 3. 索引结构
- 4. B-Tree（多路平衡查找树）
- 5. 经典B+Tree
- 6. MySQL索引数据结构中的B+Tree
- 7. Hash
1. 什么是索引？
- 索引（index）是帮助 MySQL 高效获取数据的数据结构（有序）。
2. 索引的优缺点
- 优点：
提高检索效率，降低数据库IO成本；通过索引对数据进行排序，降低数据排序成本，降低CPU的消耗。 - 缺点：
索引列占用空间；索引在提高查询效率的同时也降低了更新表的速度，在对数据表的 INSERT、UPDATE、DELETE操作时，效率降低。
3. 索引结构
MySQL 索引在存储引擎层实现，不同的存储引擎有不同的结构。
有以下存储引擎：
- B+Tree索引：最常见的索引类型，大部分引擎都支持 B+ 树索引。（平时说的索引，通常没有特别指明，都是 B+ 树索引）
- Hash索引：底层数据结构是哈希表实现的，只有精确匹配索引列的查询才有效，不支持范围查询。
- R-Tree（空间索引）：MyISM 引擎的一个特殊索引类型，主要用于地理空间数据类型，通常使用较少。
- Full-text（全文索引）：通过建立倒排索引，快速匹配文档的方式。类似于 Lucene，Solr，ES。
4. B-Tree（多路平衡查找树）
- 以一棵最大度数为5（5阶）的 b-tree 为例（每个节点最多存储4个 key，5个指针）
- 树的度数：指的是一个节点的子节点的个数
- 演示过程
先后插入元素：234、345、23、899
此时，插入元素：1200 ——> 放在899后面会导致有 5 个 key，6 个指针，不符合5阶 ——> 此时的中间元素 345 向上分裂
插入元素：10，153，600，920
此时，将要插入元素：300，1300——> 300放在234后面会导致有 5 个 key，6 个指针，不符合5阶 ——> 此时的中间元素 153 向上分裂。1300同理，中间元素920向上分裂
再依次插入元素：2，80，120 400，700，800
再依次插入元素：400，700，800 ——> 此时，在345和920之间也不符合5阶 ——> 中间元素 700 向上分裂 ——> 上面一层也不符合5阶——> 中间元素 345 向上分裂
5. 经典B+Tree
- 以一棵最大度数为 4（4阶）的b+Tree为例
- 特点：
- b+Tree中，所有元素都会出现在叶子结点，非叶子节点主要起到索引的作用
- 叶子节点之间形成了单向链表
- 演示过程（5阶）
先依次插入元素：100、65、169、368
此时，插入元素：900 ——> 中间元素169向上分裂，并且叶子节点中仍然存在元素169，与前一个叶子节点间形成链表
再插入元素：556、780
6. MySQL索引数据结构中的B+Tree
- MySQL索引数据结构对经典的B+Tree进行了优化。在原B+Tree的基础上，增加了一个指向相邻叶子节点的链表指针，形成了带有顺序的指针的B+Tree，提高区间访问的性能。
7. Hash
- 哈希索引就是采用一定的Hash算法，将键值换算成新的hash值，映射到对应的槽位上，然后存储在hash表中
- 如两个（或多个）键值，映射到同一个槽位上，就产生了hash冲突（hash碰撞），可以通过链表来解决。
- 特点：
- Hash索引只能用于对等比较(=，in)， 不支持范围查询(between, >，<, … .
- 无法利用索引完成排序操作
- 查询效率高，通常只需要一次检索就可以了， 效率通常要高于B+tree索引（若发生hash碰撞则不一定）
- 存储引擎支持：在MySQL中，支持hash索引的是Memory引擎，而innoDB中具有自适应hash功能，hash索引是存储引擎根据B+Tree索引在指定条件下自动构建的。
