为什么要有B树？
计算机有一个局部性原理，就是说，当一个数据被用到时，其附近的数据也通常会马上被使用。所以当你用红黑树的时候，你一次只能得到一个键值的信息，而用B树，可以得到最多M-1个键值的信息。这样来说B树当然更好了。
另外一方面，同样的数据，红黑树的阶数更大，B树更短，这样查找的时候当然B树更具有优势了，效率也就越高。
一、B树
B树的结构要求：
1）根节点至少有两个子节点
2）每个节点有M-1个key，并且以升序排列
3）位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间
4）其它节点至少有M/2个子节点
5）所有叶子节点都在同一层
二、B+树
B+树是B-树的变体，也是一种多路搜索树：
1.其定义基本与B-树同，除了根节点：
2.非叶子结点的子树指针与关键字个数相同；
3.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
４.为所有叶子结点增加一个链指针；
５.所有关键字都在叶子结点出现；
三、B*树
B*树是对B+树进行的又一次的升级。在B+树的非根和非叶子结点再增加指向兄弟的指针；
四、MySQl中索引的数据结构
1、MyISAM引擎
MyISAM中有两种索引，分别是主索引和辅助索引，在这里面的主索引使用具有唯一性的键值进行创建，而辅助索引中键值可以是相同的。MyISAM分别会存一个索引文件和数据文件。它的主索引是非聚集索引。当我们查询的时候我们找到叶子节点中保存的地址，然后通过地址我们找到所对应的信息。
2、InnoDB引擎
InnoDB索引和MyISAM最大的区别是它只有一个数据文件，在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点数据域保存了完整的数据记录。所以我们又把它的主索引叫做聚集索引。而它的辅助索引和MyISAM也会有所不同，它的辅助索引都是将主键作为数据域。所以，这样当我们查找的时候通过辅助索引要先找到主键，然后通过主索引再找到对于的主键，得到信息。
因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
InnoDB索引和MyISAM索引的区别：
一是主索引的区别，InnoDB的数据文件本身就是索引文件。而MyISAM的索引和数据是分开的。
二是辅助索引的区别：InnoDB的辅助索引data域存储相应记录主键的值而不是地址。而MyISAM的辅助索引和主索引没有多大区别。