索引的数学原理

索引的实现是B+树，<key data>类型的数据结构，B+树内节点不存data，只存key；叶子节点不存储指针。利用磁盘预读局部性原理，一次I\/O操作多个页(4K)到内存，数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I\/O就可以完全载入。B-Tree中一次检索最多需要h-1次I\/O（根节点常驻内存），渐进复杂度为类型的数据结构，B+树内节点不存data，只存