InnoDB一棵B+树可以存放多少行数据？
B+树经典面试题
InnoDB一棵B+树可以存放多少行数据？
为什么索引结构默认使用B+树，而不是hash，二叉树，红黑树，B-树？
B-树和B+树的区别
InnoDB一棵B+树可以存放多少行数据？
这个问题的简单回答是：约2千万行。
在计算机中，磁盘存储数据最小单元是扇区，一个扇区的大小是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层，已经满足千万级别的数据存储。
为什么索引结构默认使用B+树，而不是B-Tree，Hash哈希，二叉树，红黑树？
简单版回答如下：
Hash哈希，只适合等值查询，不适合范围查询。
一般二叉树，可能会特殊化为一个链表，相当于全表扫描。
红黑树，是一种特化的平衡二叉树，MySQL 数据量很大的时候，索引的体积也会很大，内存放不下的而从磁盘读取，树的层次太高的话，读取磁盘的次数就多了。
B-Tree，叶子节点和非叶子节点都保存数据，相同的数据量，B+树更矮壮，也是就说，相同的数据量，B+树数据结构，查询磁盘的次数会更少。
B-树和B+树的区别
B-树内部节点是保存数据的;而B+树内部节点是不保存数据的，只作索引作用，它的叶子节点才保存数据。
B+树相邻的叶子节点之间是通过链表指针连起来的，B-树却不是。
查找过程中，B-树在找到具体的数值以后就结束，而B+树则需要通过索引找到叶子结点中的数据才结束
B-树中任何一个关键字出现且只出现在一个结点中，而B+树可以出现多次。