b+tree索引在MyIsam和InnoDB的不同实现方式

普通二叉搜索树当索引的劣势：

（1）每个节点占用的空间太少，不能很好的利用磁盘的预读性

（2）数据不规律的话，很可能形成链表

（3）频繁IO

b树当索引机制相比于二叉树的优势和劣势：

（1）每个节点有关键字、数据区、子节点指针

（2）每个节点存储的数据多，可以充分的利用预读性（mysql一个磁盘页默认是16KB）

b+树相比于b树的优势：

（1）因为每个节点不存数据区（内存地址）了，所有每个节点的度可以更多，这样树的高度可以变矮很多，更利于查找

（2）数据区都在叶子节点存着，一条链表，在排序时更有优势

（3）b+树的节点变换时，是分裂形式而不是b树的左旋转(右旋转)形式，效率高

（4）但是B+树有个缺点，就是不论查什么数据都必须要遍历到叶子节点才可以拿到真实的数据地址

myisam和innodb的索引机制的不同：

（1）前者的索引和数据区是分成两个文件来分别存储的，后者的数据区是和主键索引放在一起的

（2）前者的每个索引都是单独的一棵树，每个索引都存有真实的数据区地址，而后者只有主键索引树才存有真实地址，而辅助索引树的叶子节点存的是主键的关键字

（3）前者每个索引树都可以独当一面，而后者的辅助索引树就算找到了对应的关键字，也还是要到叶子节点拿到主键的关键字，然后再去主键索引树遍历

（4）前者没有默认的主键索引，而后者有默认的主键索引（聚集索引）（不明确指定的情况下），后者除了主键索引是聚集索引，其他都是非聚集索引

巴特西