一、B+Tree

B+Tree

二、B+Tree分析

mysql使用的是B+Tree，为什么不使用B-Tree呢，主要是树结构决定的；B-Tree每个节点都有数据，B+Tree只有叶子节点存放数据，父级会保存子节点的第一个值，但是除开叶子节点，是不保存数据的；B+Tree两个连续的叶子节点会相互引用，在范围查询时会提高效率；

mysql每页数据大小是固定的16KB，所以使用B+Tree在同等数据量时，会减少树的深度，提高查询效率；所以我们建立主键时，尽量选择主键自增，会有效减少主键的深度；

上图蓝色部分为索引值，白色部分为子节点的引用，占6个字节，如果使用int类型来作为主键，一页就可以保存16KB/(8B+6B)≈1170个索引，两层树结构，就能保存1170*1170条数据；所以搜索时能用到索引能提高查询效率；查询时每次是按照页的单位来获取数据，会把一页的数据加载到内存；

如果想看B+Tree的结构，或者想看下B+Tree怎么分裂的，可以看下这个网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html