索引存储与计算
数据处理采用局部性原理
空间局部性是说，如果当前数据是正在被使用的数据，那么与该数据空间地址临近的其他数据 在未来由更大的可能性被用到，因此可以优先加载到寄存器或主存中，从而提高效率。通俗的说就是，当磁盘上的一块数据被读取的时候，我们干脆多读一点，而不是用多少读多少。
InnoDB存储引擎将数据划分为若干个页，以页作为磁盘和内存之间交互的最小单位。InnoDB中页的大小默认为16KB。也就是默认情况下，一次最少从磁盘中读取16KB的数据到内存中，一次最少把内存中16KB的内容刷新到磁盘上。 对于InnoDB的存储引擎而言所有类型的数据都是以“页”的形式进行存储的。
非常非常重要的一点是，在一个数据页中，用户记录是按照主键由小到大的顺序串联而成的单向链表。待确认：叶子结点（页）之间是双向循环链表
索引查询示例
mysql 索引采用的是 B+ 树结构来构建，B+ 树是一颗变种的 B树，变种的主要目的是减少树的深度和大小，以减少 IO 的次数，提升效率。那 B树 可以理解为是一颗平衡多叉树，所以再这种数据结构下，查找的时间复杂度可以理解为 二分查找的时间复杂度O(logn)。
如果我们要加载id=55的数据，那么
1.把磁盘块1的数据由磁盘加载到内存，发生一次IO，在内存中用二分查找确定55在50-100，锁定磁盘块1的P2指针，确定了磁盘块3的位置。
2.把磁盘块3的数据由磁盘加载到内存，发生第二次IO，确定55在50-60之间，锁定磁盘块3的P指针，确定了磁盘块7的位置。
3.加载磁盘块7的数据到内存，发生第三次IO，在内存中做二分查找确定数据55，结束查询，总计三次IO。
真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。
主键索引存储计算
InnoDB主键索引的B+tree高度为多高呢？
假设:
一行数据大小为1k，一页中可以存储16行这样的数据。InnoDB的指针占用6个字节的空间，主键即使为bigint，占用字节数为8。
高度为2：
n * 8 + (n + 1) * 6 = 16*1024 , 算出n约为 1170
现在计算一页可以存储多少个主键及指向子节点的指针。n+1 中的 +1 的意思是：指向子节点的有左右两个指针，不 是一个。
1171* 16 = 18736
也就是说，如果树的高度为2，则可以存储 18000 多条记录。
1层可以有1171 个指针，指向叶子结点，一个叶子结点可以存储 16行数据。当前个人认为 一个叶子结点的存储空间是一页，后面需要待查证。
高度为3：
1171 * 1171 * 16 = 21939856
也就是说，如果树的高度为3，则可以存储 2200w 左右的记录。