msyql 为什么要使用B+树

为什么呢

为什么不使用二叉树、平衡树、红黑树、或者B树

首先确认一点

二叉树、平衡树、红黑树、尤其是红黑树
B树
他们的搜索速度的确够快
但是运用至计算机，其速度需要受到I/O制约
所以二叉树、平衡树、红黑树的深度太深，io次数太多，浪费性能
B树是因为数据和节点保存在一起，相同数量的数据，其深度会比较大

• 为什么会比较大？
  先说明一种情况
  正常是cpu和内存进行交互，内存和磁盘进行交互
  磁盘读取是按页的，正常是4k或者8k
  节点和数据同时保存，每页保存的数量肯定会变少，为了保存更大数据量的数据，树的深度肯定会加深

  使用B+树

  B+ 树除了页子节点，所有非页子节点都不保存数据，所以每页数据可以保存非常多的数量，间接导致同深度的树能保存更多的数据

引申出的问题

分表

• 水平分表
  很容易理解，降低深度和减少数据量，就是为了降低io次数
• 垂直分表
  原理是将大字段的io效率低，那就拆分出去，本表做查询然后做关联查询
  为啥能提高速度

1. 每次查询，内存很小，可以缓存，若是使用的都是短查询的话，缓存全命中，速度极大替快
2. 数据量小了，查询肯定快
3. 内存和存储是以页进行查找和定位的，单叶内数据越多，肯定io效率越好，速度越快