数据库索引有哪些？
是否要建索引？
索引主要是帮助数据库系统高效获取数据的数据结构。
如果数据量比较少，是否使用索引对结果的影响并不大，比如数据不超过 1000 行，那么可以不建索引。
索引的种类有哪些？
按照逻辑功能上分，有普通索引，唯一索引，主键索引，全文索引。
- 普通索引是基础的索引，没有任何约束，主要用于提高查询效率。
- 唯一索引主要在普通索引的基础上，增加了唯一性的约束。
- 主键索引在唯一索引上增加了不为空的约束，也就是说 NOT NULL Unique ,一张表中最多只有一个主键索引。
- 全文索引，使用的并不多，MySQl 自带的全文索引只支持英文，通常采用专门的搜索引擎，比如 ES 和 Solar
按照物理实现方式，索引可以分2种：聚集索引和非聚集索引。
- 聚集索引可以按照主键来排序存储数据，这样在查找行的时候非常有效率。主要因为聚集索引存储的是整行数据，避免回表，二次查找。主键索引就是聚集索引。每个表只能有一个聚集索引。
- 非聚集索引，数据库会有单独的空间存放非聚集索引，这些索引项是按照顺序存储的，但是索引项指向的内容是随机存储的。系统查找数据时会进行两次查找，先找到索引，然后根据索引找到索引对应位置的数据行。
聚集索引和非聚集索引区别
- 聚集索引的叶子节点存储的是数据记录，非聚集索引存储的数据位置，非聚集索引不会影响数据表的物理存储顺序。
- 一个表只能有一个聚集索引，但是可以有多个非聚集索引。
- 聚集索引查询效率高，但是对数据插入，删除，更新等操作，比非聚集索引效率低。
索引原理
索引常见的模型有：哈希表、二叉排序树、平衡二叉树、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 树结构：
imageB 树的查找过程如下：比如要查找关键字 9
- 我们与根节点的关键字（17,35）进行比较，9小于17那么得到指针P1；
- 按照指针P1找到磁盘块2，关键字为（8,12），因为9在8和12之间，所以我们得到指针P
- 按照指针P找到磁盘块6，关键字为（9,10），然后我们找到了关键字9
B 树
B 树是在 B 树上的改进。
B 树的特点：
- 非叶子节点不存储数据，只存储索引（冗余）和指针，这样就可以存放更多的索引，树高度可以降低。
- 叶子节点包含索引字段
- 叶子节点比 B 树增加了指针连接。
- 叶子节点有双向指针连接（首位节点可通过指针连接）提供区间访问性能，范围查找。
B 树结构如下：
B 树比如，我们想要查找关键字16，查找过程如下:
- 与根节点的关键字（1,18,35）进行比较，16在1和18之间，得到指针P1（指向磁盘块2）
- 找到磁盘块2，关键字为（1,8,14），因为16大于14，所以得到指针P3（指向磁盘块7）
- 找到磁盘块7，关键字为（14,16,17），然后我们找到了关键字16，所以可以找到关键字16所对应的数据
B 树比B树 更加矮胖，因为叶子节点不存储数据，因此能够存储更多的索引，阶数更大，深度更低，和磁盘 IO 的交互更少，查询效率也更快。并且， B 树在叶子节点上，通过有序链表，方便范围查找。
MySQL 把页作为存储空间的基本单位，一个页大小一般是 16 KB 。
页结构如下:
页结构B 树结构:
B 树结构总结
要提升索引性能，主要是减少磁盘 IO 交互的次数，因此可以使用多叉树，让树形结构变得矮胖，减少磁盘交互。在页大小相同的情况下 B 树非叶子节点不存储数据，因此能有更多阶，树变得更加矮胖，磁盘交互即可减少，提升索引性能。
