InnoDB一颗B+树可以存放多少行数据？

数据库表中的数据都是存储在页里的&＃xff0c;那么一个页可以存放多少条记录呢&＃xff1f;这取决于一行记录的大小是多少&＃xff0c;假如一行数据大小是1k&＃xff0c;那么理论上一页就可以放16条数据。当然&＃xff0c;查询数据的时候&＃xff0c;MySQL也不能把所有的页都遍历一遍&＃xff0c;所以就有了索引&＃xff0c;InnoDB存储引擎用B&＃43;树的方式来构建索引。聚簇索引就是按照每张表的主键构造一颗B&＃43;树&＃xff0c;叶子节点存放的是整行记录数据&＃xff0c;在非叶子节点上存放的是键值以及指向数据页的指针&＃xff0c;同时每个数据页之间都通过一个双向链表来进行链接。

如上图所示&＃xff0c;就是一颗聚簇索引树的大致结构。它先将数据记录按照主键排序&＃xff0c;放在不同的页中&＃xff0c;下面一行是数据页。上面的非叶子节点&＃xff0c;存放主键值和一个指向页的指针。当我们通过主键来查询的时候&＃xff0c;比如id&＃61;6的条件&＃xff0c;就是通过这颗B&＃43;树来查找数据的过程。它先找到根页面(page offset&＃61;3)&＃xff0c;然后通过二分查找&＃xff0c;定位到id&＃61;6的数据在指针为5的页上。然后进一步的去page offset&＃61;5的页面上加载数据。在这里&＃xff0c;我们需要理解两件事&＃xff1a;上图中B&＃43;树的根节点(page offset&＃61;3)&＃xff0c;是固定不会变化的。只要表创建了聚簇索引&＃xff0c;它的根节点页号就被记录到某个地方了。还有一点&＃xff0c;B&＃43;树索引本身并不能直接找到具体的一条记录&＃xff0c;只能知道该记录在哪个页上&＃xff0c;数据库会把页载入到内存&＃xff0c;再通过二分查找定位到具体的记录。现在我们知道了InnoDB存储引擎最小存储单元是页&＃xff0c;在B&＃43;树索引结构里&＃xff0c;页可以放一行一行的数据(叶子节点)&＃xff0c;也可以放主键&＃43;指针(非叶子节点)。上面已经说过&＃xff0c;假如一行数据大小是1k&＃xff0c;那么理论上一页就可以放16条数据。那一页可以放多少主键&＃43;指针呢&＃xff1f;假如我们的主键id为bigint类型&＃xff0c;长度为8字节&＃xff0c;而指针大小在InnoDB源码中设置为6字节。这样算下来就是 16384 / 14 &＃61; 1170&＃xff0c;就是说一个页上可以存放1170个指针。一个指针指向一个存放记录的页&＃xff0c;一个页里可以放16条数据&＃xff0c;那么一颗高度为2的B&＃43;树就可以存放 1170 * 16&＃61;18720 条数据。同理&＃xff0c;高度为3的B&＃43;树&＃xff0c;就可以存放 1170 * 1170 * 16 &＃61; 21902400 条记录。理论上就是这样&＃xff0c;在InnoDB存储引擎中&＃xff0c;B&＃43;树的高度一般为2-4层&＃xff0c;就可以满足千万级数据的存储。查找数据的时候&＃xff0c;一次页的查找代表一次IO&＃xff0c;那我们通过主键索引查询的时候&＃xff0c;其实最多只需要2-4次IO就可以了。