一、索引的常见模型

1.1 哈希表

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。

哈希表这种结构适用于只有等值查询的场景，比如 Memcached 及其他一些 NoSQL 引擎。

1.2 有序数组

有序数组在等值查询和范围查询场景中的性能就都非常优秀。
如果仅仅看查询效率，有序数组就是最好的数据结构了。但是，在需要更新数据的时候就麻烦了，你往中间插入一个记录就必须得挪动后面所有的记录，成本太高。

有序数组索引只适用于静态存储引擎。

1.3 二叉搜索树

二叉搜索树的特点是：父节点左子树所有结点的值小于父节点的值，右子树所有结点的值大于父节点的值。

二、InnoDB 的索引模型

在 InnoDB 中，表都是根据主键顺序以索引的形式存放的，这种存储方式的表称为索引组织表。又InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的。

每一个索引在 InnoDB 里面对应一棵 B+ 树。

基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。

主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间也就越小。

适合用业务字段直接做主键的场景

  • 只有一个索引；
  • 该索引必须是唯一索引。

三、小结

B+ 树能够很好地配合磁盘的读写特性，减少单次查询的磁盘访问次数。

由于 InnoDB 是索引组织表，一般情况下建议你创建一个自增主键，这样非主键索引占用的空间最小。但事无绝对，有些场景适合使用业务逻辑字段做主键。