为什么使用B+Tree？( 三 )

B+Tree是在B-Tree基础上演进而来的。与之不同的是B+Tree的数据页只存储在叶子节点中，并且叶子节点之间通过指针相连，为双向链表结构。

本文插图
B+Tree的优点可以分为以四个：

充分利用空间局部性原理，适合磁盘存储。
树的高度很低，能够在存储大量数据情况下，进行较少的磁盘IO【见下文介绍】。
能够很好支持单值，范围查询，有序性查询。
索引和数据分开存储，让更多的索引存储在内存中。

三， MySQL中索引实现#
3.1 巧妙利用B+Tree
MySQL中的数据存储通常以Page为单位，俗称数据页，每个Page对应B+Tree的一个节点。页是InnoDB磁盘管理的最小单位，默认每个数据页的大小为16kb ，也可以通过参数innodb_page_size将页的大小设置成其他值。
数据库的页大小和操作系统类似，是指存放数据时，每一块连续区域数据的大小。比如一个1M的数据存放在数据库中时，需要大概64个页来存放（1024=64*16）。如果是在操作系统上安装的数据库，最好将数据库页大小设置为操作系统页大小的倍数，才是最佳设置。

本文插图
3.2 树的高度-有效减少磁盘IO次数
通常情况下，一张MySQL表中有成千上万条数据，而磁盘IO次数往往与数的高度成正比。默认情况下一个Page的大小为16kb ，由于每个Page中数据通过指针相连，且每个指针大小为6字节。
在工作中，我们通常使用长度为8个字节的bigint类型作为主键id的类型。已知，每一条数据都会包含一个6字节的指针（数据页中每条记录都有指向下一条记录的指针，但是没有指向上一条记录的指针）；所以一条索引数据大约占用8+6=14个字节，一个Page中能存储16 * 1024 / 14 ≈ 1170条索引数据。高度为2的B+Tree大约能存储1170*16 = 18720条这样的记录。同理，高度为3的B+Tree的B+Tree大约能存储1170 * 1170 * 16 = 21902400 ，大约两千万条数据。（每个节点大约能存储1170条记录，可以理解为此时B+Tree为1170叉树）
例如，要检索id=008的数据，则需要进行三次磁盘IO找到对应的数据页（最多三次，因为Page可能在缓存中），然后在数据页中进行二分查找，定位到对应的记录。

本文插图
四，总结#
大家耳熟能详的B+Tree索引是一种非常优秀的数据结构，也是面试热点问题。本文从数据结构和磁盘IO两个方面分析了为什么使用B+Tree ，以及MySQL的InnoDB存储引擎的索引实现。在笔者面试过程中，被问到MySQL索引时通常也是从底层数据结构特点以及结合磁盘IO两个角度去分析，屡试不爽。
学习一门技术时，我们不仅要知道其优点更要了解其缺点和瓶颈。在分析MySQL索引的实现时，不妨试试从其他数据结构的缺点入手！在Redis中使用跳表实现了有序集合Zset ，同样支持高效的顺序查询，对比MySQL索引实现，跳表能否替换B+Tree？如果不行，是因为什么呢？
作者：浪人
来源：https://www.cnblogs.com/liqiangchn/p/12995831.html