B树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-个子节点。
·根节点至少有两个子节点
·每个节点有M-个key，并且以升序排列
·位于M-和Mkey的子节点的值位于M-和Mkey对应的Value之间
·其它节点至少有M/2个子节点
下图是一个M=4阶的B树:
可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。B+树B+树是对B树的一种变形树，它与B树的差异在于：
·有k个子结点的结点必然有k个关键码；
·非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。
·树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录
B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。
B+树的优点在于：
·由于B+树在内部节点上不包含数据信息，因此在内存页中能够存放更多的key。数据存放的更加紧密，具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。
·B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。下面是B树和B+树的区别图：
分析对B树和B+树的分析和对前面讲解的2-3树的分析类似，
对于一颗节点为N度为M的子树，查找和插入需要logM-N~logM/2N次比较。这个很好证明，对于度为M的B树，每一个节点的子节点个数为M/2到M-之间，所以树的高度在logM-N至logM/2N之间。
这种效率是很高的，对于N=62*个节点，如果度为，则logM/2N=4，即在亿个元素中，如果这棵树的度为，则只需要小于4次即可定位到该节点，然后再采用二分查找即可找到要找的值。
在MySQL中，最常用的两个存储引擎是MyISAM和InnoDB，它们对索引的实现方式是不同的。
MyISAMdata存的是数据地址。索引是索引，数据是数据。
InnoDBdata存的是数据本身。索引也是数据。
了解了数据结构再看索引，一切都不费解了，只是顺着逻辑推而已。另加两种存储引擎的区别：
、MyISAM是非事务安全的，而InnoDB是事务安全的
2、MyISAM锁的粒度是表级的，而InnoDB支持行级锁
3、MyISAM支持全文类型索引，而InnoDB不支持全文索引
4、MyISAM相对简单，效率上要优于InnoDB，小型应用可以考虑使用MyISAM
5、MyISAM表保存成文件形式，跨平台使用更加方便
6、MyISAM管理非事务表，提供高速存储和检索以及全文搜索能力，如果在应用中执行大量select操作可选择
7、InnoDB用于事务处理，具有ACID事务支持等特性，如果在应用中执行大量insert和update操作，可选择。
北京JackLi喜欢作者