常见索引机制

哈希表

以键值对存储数据的结构，缺点会发生hash突出，后面跟着的链表和数组，使得哈希表结构适用于等值查询的场景。

二叉树

二叉树是搜索效率最高的，时间复杂度是 O(log(N))，为了维持 O(log(N)) 的查询复杂度，得保持这颗树是一颗平衡二叉树。

B+树：

• B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用
• B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反

mysql 索引

InnoDB 使用了 B+ 树索引模型，所以数据都是存储在 B+ 树中的

• 每一个索引在 InnoDB 里面对应一棵 B+ 树
• 根据叶子节点的内容，索引类型分为主键索引和非主键索引。
• 主键索引的叶子节点存的是整行数据。在 InnoDB 里，主键索引也被称为聚簇索引（clustered index）。
• 非主键索引的叶子节点内容是主键的值。在 InnoDB 里，非主键索引也被称为二级索引（secondary index）。

select * from T where ID=500

• 如果id 是主索引，即主键查询方式，则只需要搜索 ID 这棵 B+ 树
• 如果id 是普通索引，即非主键索引，则需要先搜索 value 索引树，得到 ID 的值为 500，再到 ID 索引树搜索一次。这个过程称为回表。也就是说，基于非主键索引的查询需要多扫描一棵索引树。因此，我们在应用中应该尽量使用主键查询。