2.二叉树结构索引 二叉树的定义： 1.任意节点左子树不为空,则左子树的值均小于根节点的值； 2.任意节点右子树不为空,则右子树的值均大于于根节点的值； 3.任意节点的左右子树也分别是二叉查找树； 4.没有键值相等的节点； 如图： 
很显然，这种结构的树查询最坏的情况就会像一个线性结构，这种结构对I/O的操作次数增加，若想减少查询次数。可以看下最好的状态，平衡二叉树。
3.平衡二叉树索引（AVL） AVL的必要条件如下： 1.必须是二叉查找树 2，每个节点的左子树和右子树的高度差至多为1 
左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二； 右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。 进一步研究平衡二叉树，如果要查询10，按照AVL的查找方法，则需要对I/0进行四次操作 
而同等数据量的情况下，B树和B+树的查找次数要少。
4.B树的索引结构 1、根节点至少有两个孩子 2、每个非根节点至少有M/2（上取整）个孩子，至多有M个孩子。 3、每个非根节点至少有M/2-1(上取整)个关键字，至多有M-1个关键字。并以升序排列；key[i]和key[i+1]之间的孩子节点的值介于key[i]和key[i+1]之间。 4、所有的叶子结点都位于同一层。 用B树的结构，查找的话，只需要对I/O进行3次操作 
5.B+树 B+树是B树的一个升级版。 新增特性 叶子节点冗余了所有的非叶子节点的key 每个叶子节点增加了一个指向相龄叶子节点的指针 
这里可以看到，虽然这里查找10，也只是和B树一样需要操作3次I/O。但是B+树将所有的非叶子节点的索引都存放在叶子节点，并且还增加了顺序访问的指针，每个叶子节点都有指向相邻叶子节点的指针，这样当其他操作或者大量数据查询时，可以大大减少对I/O磁盘的读取操作。
综上：减少对磁盘的I/O操作，所以选B+树更合适作为数据库的索引。
