数据库索引有哪些？

数据库索引有哪些？

是否要建索引？

索引主要是帮助数据库系统高效获取数据的数据结构。

如果数据量比较少，是否使用索引对结果的影响并不大，比如数据不超过 1000 行，那么可以不建索引。

索引的种类有哪些？

按照逻辑功能上分，有普通索引，唯一索引，主键索引，全文索引。

• 普通索引是基础的索引，没有任何约束，主要用于提高查询效率。
• 唯一索引主要在普通索引的基础上，增加了唯一性的约束。
• 主键索引在唯一索引上增加了不为空的约束，也就是说 NOT NULL +Unique ,一张表中最多只有一个主键索引。
• 全文索引，使用的并不多，MySQl 自带的全文索引只支持英文，通常采用专门的搜索引擎，比如 ES 和 Solar

按照物理实现方式，索引可以分2种：聚集索引和非聚集索引。

• 聚集索引可以按照主键来排序存储数据，这样在查找行的时候非常有效率。主要因为聚集索引存储的是整行数据，避免回表，二次查找。主键索引就是聚集索引。每个表只能有一个聚集索引。
• 非聚集索引，数据库会有单独的空间存放非聚集索引，这些索引项是按照顺序存储的，但是索引项指向的内容是随机存储的。系统查找数据时会进行两次查找，先找到索引，然后根据索引找到索引对应位置的数据行。

聚集索引和非聚集索引区别

1. 聚集索引的叶子节点存储的是数据记录，非聚集索引存储的数据位置，非聚集索引不会影响数据表的物理存储顺序。
2. 一个表只能有一个聚集索引，但是可以有多个非聚集索引。
3. 聚集索引查询效率高，但是对数据插入，删除，更新等操作，比非聚集索引效率低。

索引原理

索引常见的模型有：哈希表、二叉排序树、平衡二叉树、B树、B+树。

二叉排序树

二叉排序树的特点是：每个节点的左儿子小于父节点，父节点又小于右儿子。

二叉排序树搜索 key 过程:

• 如果 key 大于根节点，则从有右子树查找。
• 如果 key 小于根节点，则在左子树进行查找。
• 如果等于根节点 那么就返回即可。

二叉排序树

二叉排序树最大的问题是可能出现二叉树的深度大的问题。，如果一个是二叉树 按照 【 5 22 23 24 34 77 89 91】 这个顺序创造二叉排序树，那么树的深度会非常高。

二叉排序树

这样的二叉树就变成了一个类似链表的超过，时间复杂度不再是 O(logN) 而是 O(N) , 因此便有了平衡二叉树。

平衡二叉树

平衡二叉树的特点： 平衡二叉树的特点是左子树和右子树的高度不能超过1，也就是说，左子树和右子树也是平衡二叉树。

这样就可以保证二叉树搜索时间复杂度是O(logN)。

平衡二叉树

但是由于是二叉树，随着数据量变大，树还是会非常高的，但是如果是 M 叉数，数的高度会降低，于是有了 B 数。

B 树

B 树也叫 Balance Tree ,也称为平衡的多路搜索树。

B 树的特点：

• 叶节点具有相同深度，叶节点指正为空
• 所有索引元素不重复
• 节点中数据索引从左到右依次递增。

B 树结构：

image

B 树的查找过程如下：比如要查找关键字 9

1. 我们与根节点的关键字（17,35）进行比较，9小于17那么得到指针P1；
2. 按照指针P1找到磁盘块2，关键字为（8,12），因为9在8和12之间，所以我们得到指针P
3. 按照指针P找到磁盘块6，关键字为（9,10），然后我们找到了关键字9

B+ 树

B+ 树是在 B 树上的改进。

B+ 树的特点：

• 非叶子节点不存储数据，只存储索引（冗余）和指针，这样就可以存放更多的索引，树高度可以降低。
• 叶子节点包含索引字段
• 叶子节点比 B 树增加了指针连接。
• 叶子节点有双向指针连接（首位节点可通过指针连接）提供区间访问性能，范围查找。

B+树结构如下：

B 树

比如，我们想要查找关键字16，查找过程如下:

1. 与根节点的关键字（1,18,35）进行比较，16在1和18之间，得到指针P1（指向磁盘块2）
2. 找到磁盘块2，关键字为（1,8,14），因为16大于14，所以得到指针P3（指向磁盘块7）
3. 找到磁盘块7，关键字为（14,16,17），然后我们找到了关键字16，所以可以找到关键字16所对应的数据

B+树比B树 更加矮胖，因为叶子节点不存储数据，因此能够存储更多的索引，阶数更大，深度更低，和磁盘 IO 的交互更少，查询效率也更快。并且， B+ 树在叶子节点上，通过有序链表，方便范围查找。

MySQL 把页作为存储空间的基本单位，一个页大小一般是 16 KB 。

页结构如下:

页结构

B+树结构:

B+树结构

总结

要提升索引性能，主要是减少磁盘 IO 交互的次数，因此可以使用多叉树，让树形结构变得矮胖，减少磁盘交互。在页大小相同的情况下 B+ 树非叶子节点不存储数据，因此能有更多阶，树变得更加矮胖，磁盘交互即可减少，提升索引性能。