MyISAM: 索引存放文件数据指针(物理地址)，根据指针查询具体的记录 主键和辅助索引都是独立的，都只存放物理地址 INNODB 主键索引存放文件数据，根据主键即可查询数据 辅助索引存放主键索引值，根据辅助索引查到主键索引，再根据主键查询数据 Q: 为何innodb辅助索引存放主键索引, 不直接存放数据？ A: 待解决 myisam、innodb索引都采用B+Tree Q: 为何索引是B+Tree结构？ A: (1)hash索引, hash(key) 计算后会得到一个唯一值（地址值），这样就不能进行范围、排序查询，也不能进行多条件查询。其时间复杂度O(1) (2)二叉树，在主键自增情况下，数据库插入数据时，会导致二叉树失衡，将退化为链表，这样检索效率很低，其时间复杂度为O(n) (3)红黑树，优化二叉树不平衡问题，但在主键自增情况下，数据库插入大量数据时，红黑树也会慢慢进行偏移，红黑树较二叉树而言，只能保证不会退化为链表，其时间复杂度为O(Log2n)到O(n)之间 (4)最终采用B+Tree，支持横向扩展, 解决不平衡性索引
原文：https://www.cnblogs.com/yuefeng123/p/12377781.html