B+树在B树的基础上的一中优化,InnoDB和MylSAM存储引擎都是用B+树实现索引结构
B树的索引和关键字key-data存储在磁盘里面,然后被磁盘IO操作读入内存,如果这个data很大的话,每次加到内存中的key就会减少, 这会使得B数的高度增加,这样还是会增加磁盘IO查询
为了解决这个问题, B+树将所有数据记录节点按照键值的大小顺序存放在同一层叶子节点上, 而非叶子节点只存储key值信息,这样可以大大增加每个节点存储的key值的数量,降低B+树的高度
非叶子节点只存键值信息,所有叶子节点之间都有一个链指针,数据记录都存在叶子节点上如图:
image
InnoDB存储引擎最小的存储单元是(页), 每一页的大小是16k(即16384个字节),每一行数据大概就是1k左右,那么一页就可以存16条数据
那么在InnoDb中2层的高度的B+树能存多少条数据,我们来分析一下:
在InnoDB中每个指针为6个字节,一个键值4-8个字节(如:Id为主键 -> bigInt类型是8字节)那么加起来就是14个字节, 那么一页就能存16384 / 14 =1170个指针, 所以2层的B+树能存1170*16=18720条数据
在InnoDB在B+树高度一般为3层所以1170 * 1170 * 16= 21902400 条数据,能存千万级别的数据
