磁盘io与预读
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，
而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据
的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)，具体一页有多大数据跟操作系统有关，一般为16k，也就是我们读取一页内的数据时候，
实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。
b+树介绍
B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址，
叶子结点以上各层作为索引使用。一棵m阶的B+树定义如下:
- 1.每个结点至多有m个子女
- 2.除根结点外，每个结点至少有[m/2]个子女，根结点至少有两个子女
- 3.有k个子女的结点必有k个关键字
B+树的查找与B树不同，当索引部分某个结点的关键字与所查的关键字相等时，
并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。
关键就是b+树是叶子结点存放数据，并且是按顺序存放，叶子结点之间用双向链表连接。
b+树的竞争对手们
hash表
hash概念
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，
它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记
录的数组叫做散列表。hash是常用的数据结构，通过对数据key求得唯一hash值取余来获得数组中的位置，当hash查找单个数据时会很快。
为什么不是hash
- 1.hash查找范围值的时候就会很慢
- 2.考虑内存缓冲设计数据量大的时候数据无法一次性全部加载到内存hash而hash不是按照顺序存放就会进行多次io
红黑树
红黑树5大性质
- 性质1. 结点是红色或黑色
- 性质2. 根结点是黑色
- 性质3. 所有叶子都是黑色。（叶子是NIL结点）
- 性质4. 每个红色结点的两个子结点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）
- 性质5. 从任一节结点其每个叶子的所有路径都包含相同数目的黑色结点
红黑树的5大性质保证了搜索树的高度平衡，不会在极端情况下退化为数组
为什么不是红黑树
- 1.同样考虑内存缓冲，数据量大时红黑树无法一次性加载一颗完整的树导致性能下滑无法充分利用内存特性
- 2.数据量大的时候红黑树是二叉树，高度也会很高。
b或b-树
b树作为多路查找树，b树和b+树的区别是b树的数据是所有节点都会存放
为什么不是b树
- 1.这导致b树的范围查找会比b+树慢，因为b树的数据并不全存放到叶子节点，导致b树需要从头到其他节点查找
- 2.b树由于其他节点存储了数据占用了内存，导致存放的索引在同一高度少了很多，所以无形中增加了高度
- 3.但b树的单体查找确实优于b+树，因为不用每次都到根节点，MongoDB这种文档数据库就是用b树作为索引方便单体查找
b+树的优势
b+树的设计充分利用了内存加载的特性，恰好把一页的内容加载到内存，而一页为16kb，一个索引6bytes指针+longint8bytes
约为14bytes，也就是一页161024/14=1170个索引，往下每层即分为11701170。假设每行数据大小为1kb，那么
三层的b+树数据为1170117016=21902400大约为2000万的数据存储。读取每一层为一次io