前言
索引是帮助数据库来高效获取数据的一种排好顺序的数据结构
正文
一、数据结构
二叉查找树
定义：根节点的值大于其左子树中任意一个节点的值，小于其右节点中任意一节点的值；
优点：查找指定数据不需要遍历全表，时间效率类似二分查找；
缺点：在特殊情况下会退化成链表结构，查找尾部数据需要遍历所有数据；
平衡二叉树
定义：一种特殊的二叉查找树，它会通过自旋操作来确保各个叶子节点之间的高度差不会超过平衡因子值；
优点：即使在特殊情况下，各个叶子节点的高度不会相差太大，查找效率都接近；
缺点：需要频繁地自旋，比较耗费时间；
红黑树
定义：是一种减弱版本的平衡二叉树，放弃了追求完全平衡，而是大致平衡。每个节点不是黑色就是红色，根节点和叶子节点为黑色， 如果一个节点是红色的，则它的子节点必须是黑色的；从任意一个节点到其子节点的所有路径都包含相同数目的黑色节点；
优点：确保没有一条路径会比其它路径长出两倍；所有数据的深度都是差不多的，和平衡二叉树相比，每次插入最多只需要三次自旋就能达到平衡，从而降低了自旋频率，维护效率更高；
缺点：在大数据量的情况下，树的高度会非常高，查找叶子节点的时间效率比较低；
B-Tree
定义：B树是一种多路搜索树，并不一定是二叉的，一个节点保存多个数据，从左到右递增，所有叶子节点都位于同一层，具有相同的高度，所有数据都不重复；
优点：和二叉树相比，单个节点存储了更多的数据，因此有更多的分叉，树的高度大大降低了，因此查找数据的效率提高了；
缺点：相较于二叉树，实现比较复杂；无法很好地应付范围查找；
B+Tree
定义：和B-Tree相比，非叶子节点不存储数据，只存储冗余索引，所有的数据和索引都挪到了叶子节点上，且叶子节点之间有双向指针连接，提高区间访问的性能；
优点：因为非叶子节点不存储数据，因此单个节点可以存储更多的索引，从而有更多的分叉，也就间接地降低了整棵树的高度；更重要的是，因为叶子节点之间有双向指针，可以很好地实现范围查找；
缺点：查找每个数据都必须从根节点到叶子节点，但是因为树的高度大大降低了，因此也可以接受；
Hash
定义：一种散列算法；
优点：等值查找效率非常高，优于B+Tree；
缺点：可能会发生散列碰撞，且不能很好地应付范围查找；而B+Tree因为有叶子节点之间的双向指针，就可以很好地支持范围查找；
二、存储引擎
存储引擎是决定如何存储数据的方式，是作用于表的，每张表的存储引擎可以不同，下面是MYSQL中两个比较常见的存储引擎。
MyISAM
索引文件(MYI)和数据文件(MYD)是分离的，一次索引查询先在MYI中找到数据的存储地址，然后在MYD中根据存储地址找到该数据。
InnoDB
索引和数据是聚集存储在ibd文件中的，不用回表读取数据，效率一般比MyISAM要高。
- 聚集索引，叶子节点包含了完整的数据记录，决定了不用回表查询；
- 必须要有主键，且推荐使用自增的整型，这是为了维护B+Tree的数据结构，且比较效率更快，存储空间更小。如果没有指定主键，会自己找 唯一索引列建立主键，如果没有唯一索引列，会自动建立rowid隐藏列，这一切都是为了维护B+Tree的数据结构。
三、建立索引的建议
- 应在经常用于查询的字段上建立索引；
- 应在经常用于连接的字段上建立索引；
- 应在经常需要进行范围查找的字段上建立索引；
- 应在经常需要排序的字段上建立索引；
- 不应在查询中很少使用的字段上建立索引；
- 不应对需要经常更新的表建立过多的索引；
- 不应在数据量很小的表上建立索引；
- 不应在数据取值区分度很小的字段上建立索引；
四、附录
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html?url_type=39&object_type=webpage&pos=1
https://blog.csdn.net/wyqwilliam/article/details/82935922
