为什么MySQL的索引要使⽤B+树，⽽不是其它树？⽐如B
树？
InnoDB的⼀棵B+树可以存放多少⾏数据？
答案：约2千万
为什么是这么多？
因为这是可以算出来的，要搞清楚这个问题，先从InnoDB索引数据结构、数据组织⽅式说起。
计算机在存储数据的时候，有最⼩存储单元，这就好⽐现⾦的流通最⼩单位是⼀⽑。
在计算机中，磁盘存储数据最⼩单元是扇区，⼀个扇区的⼤⼩是512字节，⽽⽂件系统（例如XFS/EXT4）的最⼩单元是块，⼀个块的⼤⼩是4k，⽽对于InnoDB存储引擎也有⾃⼰的最⼩储存单元，页（Page），⼀个页的⼤⼩是16K。
下⾯⼏张图可以理解最⼩存储单元：
⽂件系统中⼀个⽂件⼤⼩只有1个字节，但不得不占磁盘上4KB的空间。
InnoDB的所有数据⽂件（后缀为ibd的⽂件），⼤⼩始终都是16384（16k）的整数倍。
磁盘扇区、⽂件系统、InnoDB存储引擎都有各⾃的最⼩存储单元。
在MySQL中，InnoDB页的⼤⼩默认是16k，当然也可以通过参数设置：
表中的数据都是存储在页中的，所以⼀个页中能存储多少⾏数据呢？
假设⼀⾏数据的⼤⼩是1k，那么⼀个页可以存放16⾏这样的数据。
如果数据库只按这样的⽅式存储，如何查数据就成为⼀个问题，因为不知道要查的数据存在哪个页中，也不可能把所有的页遍历⼀遍，那样太慢了。
不过，可以使⽤B+树的⽅式组织这些数据，如图所⽰：
先将数据记录按主键进⾏排序，分别存放在不同的页中（为了便于理解这⾥⼀个页中只存放3条记录，实际情况可以存放很多）
除了存放数据的页以外，还有存放键值+指针的页，如图中page number=3的页，该页存放键值和指向数据页的指针，这样的页由N个键值+指针组成。
当然它也是排好序的。这样的数据组织形式，我们称为索引组织表。
现在来看下，要查⼀条数据，怎么查？
如：select * from user where id=5;
这⾥id是主键，通过这棵B+树来查，⾸先到根页，你怎么知道user表的根页在哪呢？
其实每张表的根页位置在表空间⽂件中是固定的，即page number=3的页。
到根页后通过⼆分查法，定位到id=5的数据应该在指针P5指向的页中，那么进⼀步去page number=5的页中查，同样通过⼆分查询法即可到id=5的记录：
| 5 | zhao2 | 27 |
现在清楚了InnoDB中主键索引B+树是如何组织数据、查询数据的。
总结⼀下：
InnoDB存储引擎的最⼩存储单元是页，页可以⽤于存放数据也可以⽤于存放键值+指针，在B+树中叶⼦节点存放数据，⾮叶⼦节点存放键值+指针。
索引组织表通过⾮叶⼦节点的⼆分查法以及指针确定数据在哪个页中，进⽽在去数据页中查到需要的数据；数学中的dimension
那么回到我们开始的问题，通常⼀棵B+树可以存放多少⾏数据？
这⾥我们先假设B+树⾼为2，即存在⼀个根节点和若⼲个叶⼦节点，那么这棵B+树的存放总记录数为：根节点指针数*单个叶⼦节点记录⾏数。
上⽂已经说明单个叶⼦节点（页）中的记录数=16K/1K=16。（这⾥假设⼀⾏记录的数据⼤⼩为1k，实际上现在很多互联⽹业务数据记录⼤⼩通常就是1K左右）。
那么现在需要计算出⾮叶⼦节点能存放多少指针？
其实这也很好算，假设主键ID为bigint类型，长度为8字节，⽽指针⼤⼩在InnoDB源码中设置为6字节，这样⼀共14字节sql server select into
我们⼀个页中能存放多少这样的单元，其实就代表有多少指针，即16384/14=1170。
chage命令详解那么可以算出⼀棵⾼度为2的B+树，能存放1170*16=18720条这样的数据记录。
根据同样的原理可以算出⼀个⾼度为3的B+树可以存放：1170117016=21902400条这样的记录。
所以在InnoDB中B+树⾼度⼀般为1-3层，它就能满⾜千万级的数据存储。
在查数据时，⼀次页的查代表⼀次IO，所以通过主键索引查询通常只需要1-3次IO操作即可查到数据。
怎么得到InnoDB主键索引B+树的⾼度？
上⾯通过推断得出B+树的⾼度通常是1-3，下⾯从另外⼀个侧⾯证明这个结论。
在InnoDB的表空间⽂件中，约定page number为3的代表主键索引的根页，⽽在根页偏移量为64的地⽅存放了该B+树的page level。
mysql面试题基础知识如果page level为1，树⾼为2，page level为2，则树⾼为3。即B+树的⾼度=page level+1；下⾯将从实际环境中尝试到这个page level。
在实际操作之前，可以通过InnoDB元数据表确认主键索引根页的page number为3，也可以从《InnoDB存储引擎》这本书中得到确认。
可以看出数据库dbt3下的customer表、lineitem表主键索引根页的page number均为3，⽽其他的⼆级索引page number为4。
关于⼆级索引与主键索引的区别请参考MySQL相关书籍，本⽂不在此介绍。
下⾯对数据库表空间⽂件做想相关的解析：
数据滚动代码
因为主键索引B+树的根页在整个表空间⽂件中的第3个页开始，所以可以算出它在⽂件中的偏移量：16384*3=49152（16384为页⼤⼩）。
另外根据《InnoDB存储引擎》中描述在根页的64偏移量位置前2个字节，保存了page level的值
因此我想要的page level的值在整个⽂件中的偏移量为：16384*3+64=49152+64=49216，前2个字节中。
接下来⽤hexdump⼯具，查看表空间⽂件指定偏移量上的数据：
linetem表的page level为2，B+树⾼度为page level+1=3；
region表的page level为0，B+树⾼度为page level+1=1；
customer表的page level为2，B+树⾼度为page level+1=3；
这三张表的数据量如下：
总结：
lineitem表的数据⾏数为600多万，B+树⾼度为3，customer表数据⾏数只有15万，B+树⾼度也为3。可以看出尽管数据量差异较⼤，这两个表树的⾼度都是3
换句话说这两个表通过索引查询效率并没有太⼤差异，因为都只需要做3次IO。那么如果有⼀张表⾏数是⼀千万，那么他的B+树⾼度依旧是3，查询效率仍然不会相差太⼤。
region表只有5⾏数据，当然他的B+树⾼度为1。
⾯试题
有⼀道MySQL的⾯试题，为什么MySQL的索引要使⽤B+树⽽不是其它树形结构?⽐如B树？
printf()这个问题的复杂版本可以参考本⽂；
简单回答是：
因为B树不管叶⼦节点还是⾮叶⼦节点，都会保存数据，这样导致在⾮叶⼦节点中能保存的指针数量变少（有些资料也称为扇出）
指针少的情况下要保存⼤量数据，只能增加树的⾼度，导致IO操作变多，查询性能变低；
⼩结
本⽂从⼀个问题出发，逐步介绍了InnoDB索引组织表的原理、查询⽅式，并结合已有知识，回答该问题，结合实践来证明。
当然为了表述简单易懂，⽂中忽略了⼀些细枝末节，⽐如⼀个页中不可能所有空间都⽤于存放数据，它还会存放⼀些少量的其他字段⽐如page level，index number等等，另外还有页的填充因⼦也导致⼀个页不可能全部⽤于保存数据。
参考博客：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。