B树索引
磁盘IO读数据到内存
malloc/new 向 kernel申请4B空间，实际系统可能给2个页面空间即8KB，剩下8KB-4B空间由 lib.so 或libc++.so 的 ptmalloc 或tcmalloc管理 。这样就不需要每次去kernel申请内存
磁盘IO同理，我们读一部分数据会把一整块（16KB）的内容读下来，而不是需要多少读多少，一般会多读一些。
2000W数据构建AVL树，层数是25层（log2(2000W)），查找最多25次磁盘IO。二叉树是一个节点是数据域两个指针域
如果用500阶B树则只需要3层，即查找最多需要3次IO。500叉树就是499个数据域，500个指针域
使用索引查询流程/原理【面试题】
如 select * from student where uid=5;
执行流程：
- 检查uid有索引
- 然后去存储引擎请求
kernel进行磁盘IO读取索引文件到内存上 - 最后用索引构建B树进行加速搜索
B+树索引
MySQL索引为什么最终是采用B+树呢？
因为B-树有如下缺点：
- 索引+数据的内容分散在不同的节点上，离根节点近就搜索的快，离根节点远就搜的慢，花费的磁盘IO次数不平均，每一行数据搜索花费时间也不平均；
- 每一个非叶节点上，不仅要存索引(
key) 还要存储索引值所在行的data数据。导致一个节点能存的索引不够多； - B-树不方便做范围搜索，整表搜索也不方便。
与此对比，B+树有如下的特点：
- 每一个非叶节点上，只存key，好处就是一个节点存的key更多，相同数据量层数可能更低，搜索的效率会有所提升；
- 叶子节点存储了所有索引值，搜索每个索引对应的data值，都要到叶子节点上，这样每一行搜索的时间是比较平均的；
- 在B-树上如果做区间查找，遍历的节点是非常多的，而B+树所有叶子节点被连接成了有序链表结构，因此做整表遍历和区间查找是非常容易的
