B/B+树与mysql索引

数据结构操作网站：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

B树

算法	平均	最差
空间	O(n)	O(n)
搜索	O(log n)	O(log n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)

B+树

算法	平均	最差
空间	O(n)	O(n)
搜索	O(log n)	O(log n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找

B/B+树一些区别和特点

• B树中搜索时，离根节点近的节点找的就快，离根节点远的节点找的就慢，查找数据花费的时间不稳定。B+树所有的数据都在叶子节点，查找数据花费的时间稳定

• B树的所有结点都存储数据；B+树只有叶子结点存储数据，非叶子结点只存储key

局部性原理

当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间) ，因此对于具有局部性的程序来说，磁盘预读可以提高1/0效率。预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(在许多操作系统中，页得大小通常为4k) ，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

局部性原理

• 时间局部性（Temporal Locality）：如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。程序循环、堆栈等是产生时间局部性的原因。

• 空间局部性（Spatial Locality）：在最近的将来将用到的信息很可能与正在使用的信息在空间地址上是临近的。

• 顺序局部性（Order Locality）：在典型程序中，除转移类指令外，大部分指令是顺序进行的。顺序执行和非顺序执行的比例大致是5:1。此外，对大型数组访问也是顺序的。指令的顺序执行、数组的连续存放等是产生顺序局部性的原因。

对于磁盘IO: 当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间) ，因此对于具有局部性的程序来说，磁盘预读可以提高1/0效率。预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页(在许多操作系统中，页得大小通常为4k) ，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

B+树适合索引

• 相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少，磁盘IO少
• B+树所有的叶子节点数据构成了一个有序链表，在范围区间查询数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高(即局部性原理)

B+树一般几层？

innoDB 中页的默认大小是 16KB

假设一行记录的数据大小为1k，那么单个叶子节点（页）中的记录数=16K/1K=16

非叶子节点能存放多少指针？假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，这样一共14字节，一个页中能存放多少这样的单元，其实就代表有多少指针，即16kb/14b=1170；那么可以算出一棵高度为2的B+树，大概能存放1170*16=18720条这样的数据记录(即1170个索引，每个索引定位叶子节点的一页数据，一页能存储16行原始数据)。

根据同样的原理我们可以算出一个高度为3的B+树大概可以存放：1170*1170*16=21,902,400行数据。所以在InnoDB中B+树高度一般为1-3层，它就能满足千万级的数据存储。在查找数据时一次页的查找代表一次IO，所以通过主键索引查询通常只需要1-3次逻辑IO操作即可查找到数据。