索引是一种用于快速查找和检索数据的数据结构，类似于图书的目录，通过索引可以更快地找到对应的数据。

索引的优缺点

优点：

  • 提高了查找的效率
  • 通过创建唯一性索引，确保了每一行数据的唯一性。

缺点：

  • 索引使用物理文件存储，带来了空间的消耗。
  • 创建和维护索引需要耗费时间。当数据发生更改时，索引也会动态修改，降低SQL执行效率。

索引SQL

查看索引

1
show 索引名 from 表名(列名);

image-20221128161811672

创建索引

1
create index 索引名 on 表名(列名);

image-20221128162120786

删除索引

1
drop index 索引名 on 表名

image-20221128162440340

索引底层的数据结构

索引是一种查找更快的数据结果。

数组和链表的查找都需要遍历，最先淘汰。

二叉搜索树最坏情况下会变成单支树，查找的时间复杂度变为O(N)，淘汰。

AVL树和红黑树使得左右子树高度相对平衡，但数据量太大时，树的高度过高，比较次数过多，即磁盘IO过多，淘汰。

哈希表查找的时间复杂度是O(1)，是不是可以作为索引的数据结构了呢？NO！哈希表不支持顺序和范围查找，而SQL要经常进行排序和

范围查询，淘汰。

目前大多数数据库采用B树或B+树作为索引结构，在MySQL中，MyISAM 引擎和 InnoDB 引擎都是使用 B+树 作为索引结构。

B树称为多路平衡查找树，B+树是在B树基础上的变现，二者都是多叉平衡树。

B树

image-20221128203706890

B+树

image-20221128203611266

区别和联系

  • B树N个值，划分为N+1个结点；B+树N个值，划分为N个结点。

  • B树叶子结点相互独立;B+树叶子结点是链式结构，指向相邻结点。

  • B树每个结点既存放key，又存放data；B+树只有叶子结点既存放key，又存放data，其他结点只存key。

  • B树的查找过程是对每个关键字二分查找，可能没有到叶子结点就检索到了；B+树更加稳定，每次查找都是从根节点开始，到叶子结点结束。

索引为什么要用B+树

  • 每次都是从根节点到叶子结点，IO次数都差不多，查询效率稳定。
  • 磁盘IO请求数少，查询速度快。
  • 叶子结点采用链式存储结构，方便数据范围查询。
  • 非叶子结点只存储key，占用空间小，甚至可以缓存到内存中。