如果没有特殊说明，通常大多数数据库采用的索引都是 B+ tree 索引，它是基于 B+ tree 这种数据结构构建的。为什么采用 B+ tree 而不是平衡二叉树 (AVL) 或红黑树等数据结构？这里假设索引为 1-16 的自增数据，各类数据结构的表现如下：
平衡二叉树数据结构：
红黑树数据结构：
Btree 数据结构：
B+ Tree 数据结构
以上图片均通过数据结构可视化网站 Data Structure Visualizations 自动生成，感兴趣的小伙伴也可自行尝试。
从上面的图示中我们可以看出 B+ Tree 树具有以下优点：
B+ Tree 树的所有非叶子节点 (如 003，007)，都会在叶子节点冗余一份，所有叶子节点按照链表的方式进行组织，这样带来的好处是在范围查询中，只需要通过遍历叶子节点就可以获取到所有的索引信息。
B+ Tree 的所有非叶子节点都可以存储多个数据值，存储量取决于节点的大小，在 MySQL 中每个节点的大小为 16K ，因此其具备更大的出度，即在相同的数据量下，其树的高度更低。
所有非叶子节点都只存储索引值，不存储实际的数据，只有叶子节点才会存储指针信息或数据信息。按照每个节点为 16K 的大小计算，对于千万级别的数据，其树的高度通常都在 3~6 左右 (取决于索引值的字节数)，因此其查询性能非常优异。
叶子节点存储的数据取决于不同数据库的实现，对于 MySQL 来说，取决于使用的存储引擎和是否是主键索引。
2.2 B+ tree 索引对于 InnoDB ，因为主键索引是聚集索引，所以其叶子节点存储的就是实际的数据。而非主键索引存储的则是主键的值 ：
对于 MyISAM，因为主键索引是非聚集索引，所以其叶子节点存储的只是指向数据位置的指针：
综上所述，B+ tree 结构普遍适用于范围查找，优化排序和分组等操作。B+ tree 是基于字典序进行构建的，因此其适用于以下查询：
全值匹配：以索引为条件进行精确查找。如 emp_no 字段为索引，查询条件为 emp_no = 10008。
前缀匹配：以联合索引的前缀为查找条件。如 emp_no 和 dept_no 为联合索引，查找条件为 emp_no = 10008。
列前缀匹配：匹配索引列的值的开头部分。如 dept_no 为索引，查询条件为 dept_no like "d1%"。前缀匹配和列前缀匹配都是索引前缀性的体现，在某些时候也称为前缀索引。
匹配范围值：按照索引列匹配一定范围内的值。如 emp_no 字段为索引，查询条件为 emp_no > 10008。
只访问索引的查询：如 emp_no 字段为索引，查询语句为 select emp_no from employees，此时 emp_no 索引被称为本次查询的覆盖索引，即只需要从索引上就可以获取全部的查询信息，而不必访问实际表中的数据。
精确匹配某一列并范围匹配某一列：如 emp_no 和 dept_no 为联合索引，查找条件为 dept_no = "d004" and emp_no < 10020，这种情况下索引顺序可以是（emp_no, dept_no），也可以是（dept_no, emp_no），使用 EXPLAIN 来分析的话，其 TYPE 类型都是 range（使用索引进行范围扫描），但（dept_no, emp_no）性能更好。
2.3 哈希索引