设计索引

一个简单的索引设计方案

• 下一个数据页中用户记录的主键值必须大于上一个数据页中用户记录的主键值。
  

• 给所有的页建立一个目录项。
  由于数据页在物理存储上是不连续的，如果想从多个数据页中根据该记录的主键值快速定位该记录的所在页，就需要建立一个目录页，每一个数据页对应一个目录项（目录项在物理存储器上连续存储），每个目录项包括两部分：key（数据页的用户记录中最小的主键值）、page_no（数据页的编号）。
  
  查找主键值为20的记录，分为两步：
第一步（确定页）：先从目录页中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 <209），它对应的页是页9。
第二步（确定记录）：在页中使用二分法找到主键值为20的记录。

INNODB的索引方案