这些问题是在实现索引时遇到的，我利用B+树实现了索引，整个索引包括以下三个部分：B+树结点，关键字和链接结点。B+树结点存储在索引页中。链接结点是为了解决重复关键字的问题而设计的，所有重复关键字的数据行在数据页的地址在B+树的叶结点以单链表的形式链接起来，其实就是拉链法解决冲突，整个链表保存在链接页中。

         B+树的key域是一个64位的数据类型，只能保存整型或者实型的关键字，因此要实现对字符串类型的字段或者多字段的复合索引，只能将被索引的字段值提出来作为关键字单独保存在关键字页中，然后用key域存储该关键字在关键字页中的地址，下面是一张图，描述了各个结构之间的联系。

       该索引的查找过程是，从根节点开始，用二分查找找到当前结点第一个大于等于key的关键字，然后再继续查找该关键字的孩子结点，直到搜索到叶结点。

        实现上述索引结构后，我用350W行的表进行了索引查找效率测试，发现在某些情况下，定位一数据行的缺页次数竟然达到了20多次，而相同情况下mysql索引定位一数据行的缺页次数不超过7次。经过分析，在最坏的情况下，在包含N个关键字，阶为2d+1的上述结构的索引中查找一个关键字的缺页次数是log(2)(d)*log(d)(N)+ log(d)(N)= log(2)(N)+log(d)(N)次，当N=350W，d=10时缺页次数是37次。这样的I/O次数是不可以容忍的，效率很低。

        查找上述索引结构时，多数的时间花在读取B+树结点的关键字上，为了避免这种情况，可以将关键字直接保存在B+树结点的key域中，这样最坏情况下的缺页次数为log(d)(N)，缺页次数仅为7次左右，但由于B+树结点不能跨页存储，因此必须对关键字的长度进行限制。myisam中关键字的长度必须小于767，而mysql页的容量是16K，假如每页只存储一个B+树结点，那么myisam中B+树的阶最大也就是21左右。

        我把B+树结点改为上图结构，再对350W行数据建立索引，发现整个索引的尺寸竟然超过了5G，原因是key域是定长的，绝大部分的关键字也就是十几字节，大多数的空间都被浪费了。为解决这种空间利用率太低的问题，我可以把key设定为变长的，但如果key域是变长的，那么在B+树结点a和b合并时，肯定会发生因为空间限制不能将b合并到a中，必须新申请个c，然后将a,b拷贝到c中的情况，这样会使索引页中的碎片很多，降低索引的效率，因此非常纠结。

        到这里，我有一个疑问，innodb的辅助B+树索引中页结点和非页结点的key域存储的是什么？，是如何组织的？