今天在学习mysql的过程中发现mysql在建立索引的时候，索引类型类型分为BTREE和HASH。顺便学习了一下BTREE的结构。
一棵m阶的B 树 (m叉树)的特性如下：
- 树中每个结点最多含有m个孩子（m>=2）；
- 除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；
- 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；
- 每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：
a) Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。
b) Pi为指向子树根的接点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。 c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。关键在于第5点，BTREE的每个节点存储了2组信息，一组为按照升序排列的数据，另一组为子节点的指针。比如节点数据为1、5，子节点指针为p1、p2、p3，那么p1指向的节点数据都小于1，p2指向的节点数据在1，5之间，p3指向的节点大于5。
感觉和平衡二叉树差不多，不同在于平衡二叉树只有左右子节点，一个小于根节点一个大于根节点。BTREE多用于磁盘存储设备。时间复杂度为O(logN)，和二叉树不同在于一次IO(即读入一个节点)可以读入多个数据，减少IO次数。