索引

索引是帮助数据库高效获取数据的排好序的数据结构。

有无索引时，查询的区别

主要区别在于查询速度和系统资源的消耗。

1. 查询速度：

   在没有索引的情况下，数据库需要对表中的所有记录进行扫描，以找到符合查询条件的记录，这个过程可能会非常耗时，特别是对于大表来说。

   如果有索引，数据库可以通过索引快速定位到符合查询条件的记录，大大减少了查询时间。

2. 系统资源消耗：

   无索引时，由于需要扫描整个表，因此会占用大量的系统资源，如CPU、内存等。

   有索引时，由于只需扫描索引，所以系统资源的消耗相对较小。

注意：索引并不是越多越好。过多的索引会增加数据库的空间开销，同时也可能导致查询性能下降。
也会降低更新表的速度，如对表进行INSERT、UPDATE、DELETE时，效率降低

索引结构

常见的索引结构：

二叉树

二叉树索引结构是一种基于排序二叉树的索引方法。树中每个节点的值大于其左子树中任意节点的值，小于其右子树中任意节点的值。

优点

查找效率高，特别是在数据量较大时，查找性能的优势更为明显。

局限性

二叉树索引最理想的状态，即主键插入构成的排序二叉树为完全二叉树，即叶子节点都在最后一层，这样二叉树的查询效率最高。如下图所示

但如果主键是顺序插入的，则会出现一条单向链表，也就是最极端的情况。

（此时查询的情况就跟无索引时一样了，需要通过遍历整列数据来得到查询结果）

所以二叉树的局限性在于它的高度（层次）不可控，影响因素高。

二叉树的缺点：

• 顺序插入时，会形成一个链表，查询性能大大降低。

• 大数据量情况下，层级较深，检索速度慢。

红黑树

红黑树是一种自平衡的二叉查找树，它通过一定的规则使得树保持大致平衡，从而提高了查找效率。

二叉树改良，但还是存在大数据量情况下，层级较深，检索速度慢的问题。

B-Tree

B-Tree是一种自平衡的多路查找树。

（其中B是Balanced （平衡）的意思，节点最大的孩子数目m称为B-Tree的阶（order）。）

但是，由于每个节点同时存储了数据和索引，所以每个节点所能存储的数据较少，浪费了一定的存储空间。

特点

• 在B-Tree中，非叶子节点和叶子节点都会存放数据。
• 在B-Tree中，每个内部节点（非叶子节点）存储的key数量等于它的阶数减一，对应的指针数量等于它的阶数.
• 一旦节点存储的key数量到达阶数，就会裂变，中间元素向上分裂。

B+Tree

B+Tree和B-Tree十分类似。

B+Tree的特点在于：

• 所有的数据都会出现在叶子节点。
• 叶子节点形成一个单向链表。
• 非叶子节点仅仅起到索引数据作用，具体的数据都是在叶子节点存放的。

所以B+Tree更有优势

• 更好的磁盘读写性能
• 更好的范围查找性能

优化

在MySQL中，索引数据结构对经典的B+Tree进行了优化，这种优化主要是增加了指向相邻叶子节点的链表指针，形成了带有顺序指针的B+Tree。

提高区间访问的性能，当在查找某个范围内的数据时，可以直接通过这些顺序指针快速跳转到下一个叶子节点，而不必逐级向上查找。

Hash

Hash索引是一种基于哈希表实现的索引结构。其基本思想是，对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

在哈希索引中，数据的存储和查找都是基于哈希函数进行的。哈希函数可以将任意长度的输入（也叫做“键”）通过散列算法，变换成固定长度的散列值（也叫做“哈希值”）。这个哈希值就是我们在哈希索引中用来定位数据的地址。

当我们需要查找某一行的数据时，只需要根据这一行的主键值计算出相应的哈希值，然后在哈希表中查找这个哈希值所对应的指针，再通过这个指针就可以快速找到这一行的数据。因此，哈希索引的查找效率是非常高的，基本上可以达到O(1)的时间复杂度。

特点

• Hash索引只能用于对等比较(=，in)，不支持范围查询（between，>，< ，…）
• 无法利用索引完成排序操作
• 查询效率高，通常(不存在hash冲突的情况)只需要一次检索就可以了，效率通常要高于B+tree索引