知识点 | InnoDB一棵B+树可以存放多少行数据？& 为什么索引结构默认使用B+树？

以下文章节选自如下链接。根据文章内容做了内容解说和扩容。
https://baijiahao.baidu.com/s?id=1692469218111984631&wfr=spider&for=pc

B+树是B-树的变体，也是一颗多路搜索树。一棵m阶的B+树主要有这些特点：

1. 每个结点至多有m个子女;
2. 非根节点关键值个数范围：m/2 <= k <= m-1相邻叶子节点是通过指针连起来的，并且是关键字大小排序的。
   B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
   B+树相邻的叶子节点之间是通过链表指针连起来。

InnoDB一棵B+树可以存放多少行数据？
在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是512字节。文件系统中，最小单位是块，一个块大小就是4k；InnoDB存储引擎最小储存单元是页，一页大小就是16k。

因为B+树叶子存的是数据，内部节点存的是键值+指针。索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而再去数据页中找到需要的数据。叶子节点存放所有的数据库行信息。
假设B+树的高度为2的话，即有一个根结点和若干个叶子结点。这棵B+树的存放总记录数为=根结点指针数*单个叶子节点记录行数。

如果一行记录的数据大小为1k，那么单个叶子节点可以存的记录数 =16k/1k =16.非叶子节点内存放多少指针呢？我们假设主键ID为bigint类型，长度为8字节，而指针大小在InnoDB源码中设置为6字节，所以就是8+6=14字节，16k/14B =16*1024B/14B = 1170

因此，一棵高度为2的B+树，能存放1170 16=18720条这样的数据记录。同理一棵高度为3的B+树，能存放1170 1170 *16 =21902400，也就是说，可以存放两千万左右的记录。B+树高度一般为1-3层，已经满足千万级别的数据存储。

注意：按照上述计算，如果是此表全量加载到内存中，需要的内存为：叶子结点数，也是 InnoDB的页数( 1170 1170) 16 (单页所能存放的行数)* 1KB（每行大小）/1024/1024=21GB。
这里的两千万评估值和每行的数据大小成反比，和页面大小成正比，和内存大小成正比。

还要注意下：

1. 如果 InnoDB 页面过大，而内存又不够的情况下，当访问大量数据时，可能存在频繁的内存换出和换入，导致检索效率反而下降。
2. 故OLTP类库采用 InnoDB默认的页面大小16K即可，OLAP类因数据顺序存储，可适当调大InnoDB页大小到64KB，内存也须响应放大。

为什么索引结构默认使用B+树，而不是B-Tree，Hash哈希，二叉树，红黑树？
简单版回答如下：1. Hash哈希，只适合等值查询，不适合范围查询。

1. 一般二叉树，可能会特殊化为一个链表，相当于全表扫描。
2. 红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘次数多。
3. B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说。相同的数据量，B+树数据结构，查询磁盘的次数会更少。