Shu Ju Jie Gou
完全二叉树：若设二叉树的深度为 h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边（效率高）满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树二叉搜索树（二叉排序树，二叉查找树）树中每个节点最多有两个子树，通常称为左子树和右子树若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值它的左右子树仍然是一棵二叉搜索树 (recursive)平衡树(B树)排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；子节点数：1<非叶节点的子节点数<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路, 当M=2则是2叉树, M=3则是3叉）关键字数：ceil(m/2)-1<=枝节点的关键字数量<=M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子B+树特点B+树的非叶子节点不保存关键字记录的指针，只进行数据索引（非叶子节点所能保存的关键字大大增加）B+树叶子节点保存父节点的所有关键字记录的指针，数据地址必须要到叶子节点才能获取到（每次数据查询的次数都一样）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针非叶子节点的子节点数=关键字数（两种实现，或：非叶节点的关键字数=子节点数-1。Mysql 的B+树是第一种）与红黑树的比较（访问磁盘数据有更高的性能）B+ 树有更低的树高
磁盘访问原理：操作系统一般将内存和磁盘分割成固定大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点。
如果数据不在同一个磁盘块上，那么通常需要移动制动手臂进行寻道，而制动手臂因为其物理结构导致了移动效率低下，从而增加磁盘数据读取时间。B+ 树相对于红黑树有更低的树高，进行寻道的次数与树高成正比，在同一个磁盘块上进行访问只需要很短的磁盘旋转时间，所以 B+ 树更适合磁盘数据的读取
为了减少磁盘 I/O 操作，磁盘往往不是严格按需读取，而是每次都会预读。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的磁盘旋转时间，速度会非常快。并且可以利用预读特性，相邻的节点也能够被预先载入
平衡二叉树（AVL 树）：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树红黑树黑色完美平衡：任意一个结点到到每个叶子结点的路径都包含数量相同的黑结点