MySQL索引数据结构入门( 二 ) _MySQL

B+Tree 中，由于分支节点只保存索引数据和指向下一个节点的指针，所以在相同的磁盘空间中，能够指向更多的子节点，这就意味树的高度更低，搜索所需要的 IO 次数更少，搜索效率更高。

B-Tree 中，由于分支节点不仅保存索引数据和指向下一个节点的指针，还保存了指向具体数据的指针，所以在相同的空间下能够指向的子节点数量就少于 B+Tree，这就意味着相同的数据量，B-Tree 树高更高，搜索所需的 IO 次数更多，搜索效率低。

B+Tree 叶子节点的关键字从小到大按顺序排列，左边结尾数据都会保存右边节点开始数据的指针（红色区域），这个指针在范围搜索的时候非常有用，例如想搜索姓名在 ac～bc 之间的数据，按照树找到第一个节点 ac 之后，顺着指针一直往后找，找到第一个不满足条件的数据结束。

如果是 B-Tree 则没有 ac 指向 bc 的指针，需要先回到分支节点 af 再继续向下搜索，效率就会低很多。

B+Tree 的叶子节点都是有序排列的，所以 B+Tree 对于数据的排序有着更好的支持。

B-Tree 由于有一部分数据保存在分支节点中，叶子节点并不是完整的数据，所以对于排序、范围搜索的支持并不如 B+Tree 。

B+Tree 数据划分的原则是左闭右开，以 (af,88) 这个节点为例，小于 (af,88) 节点的在左边，大于等于 (af,88) 节点的在右边。

B-Tree 则是左开右开。

B+Tree 全表扫描更快，因为所有数据都出现在叶子节点上，并且叶子节点之间还有指针相连，直接遍历即可。

B-Tree 在全表扫描的时候则需要对树的每一层进行遍历才能读到所有数据。

叶子节点指向数据的指针，如果是聚簇索引，则指向的是表中一条完整的记录；如果是非聚簇索引，则指向的是具体的主键值。在以非聚簇索引为依据进行搜索的时候，先找到记录的主键值，再根据主键值去聚簇索引找到完整的记录，这个过程就是回表（InnoDB 中）。

好了，相信通过上面八点的介绍，大家对于 B-Tree 和 B+Tree 已经有了基本的认知了。
当我们想要搜索一条记录的时候，顺着根节点从上往下扫描树，比直接遍历一条一条的记录显然是要快很多。
说一个不太恰当的比喻，MySQL 中的数据存储，就像是通过一个链表把所有数据按照顺序串到一起，然后在这个链表上面又架了一个多路平衡查找树的感觉，搜索的时候，按照链表一个一个找，就是全表扫描；从树的根节点开始找，就是用索引。
2.2 树高问题一个经典的问题，高度为 3 的 B+Tree 大概可以保存多少条数据？
计算机在存储数据的时候，最小存储单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如 XFS/EXT4）最小单元是块，一个块的大小是 4KB 。但是 InnoDB 在进行磁盘操作的时候，并不是以扇区或者块为依据的，InnoDB 在进行磁盘操作的时候，是以页为单位的，有时候也称作逻辑页，每个逻辑页的大小默认是 16KB，即四个块。这就意味着，InnoDB 在实际操作磁盘的时候，每次从磁盘上读取数据，至少读取 16KB，每次向磁盘上写数据，也至少写 16KB，并不是你需要 1KB 就读取 1KB，即使你只需要 1KB 的数据，InnoDB 也会从磁盘中将 16KB 的数据读取到内存中。
通过如下命令我们可以查看 MySQL 中 InnoDB 存储引擎逻辑页的大小：

文章插图
16384/16=1024
前面的结论没问题。
以聚簇索引为例，现在我们假设数据库中一条记录的大小是 1KB，那么一个逻辑页就可以存 16 条数据（叶子节点）。
对于非叶子节点存储的则是主键值+指针，在 InnoDB 中，一个指针的大小是 6 个字节，假设我们的主键是 bigint，那么主键占 8 个字节，当然还有其他一些头信息也会占用字节我们这里就不考虑了，我们大概算一下，小伙伴们心里有数即可：
16*1024/(8+6)=1170
即一个非叶子节点可以指向 1170 个子节点，那么一个三层的 B+Tree 可以存储的数据量为：