B+数¶
一个m阶的B+树具有如下几个特征： - B+树的阶数反应了树的横向规模： - 中间节点都至少包含：ceil(m / 2)个孩子，最多有m个孩子 - 叶子节点都包含：k个元素，其中 m/2 <= k <= m-1 - 所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小，自小而大顺序链接 - 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素
PS：B+数的规模由阶数和高度同时决定
B+树和数据库索引¶
数据页是数据库的最小存储管理单元，通常一个数据页为16K，假设一行数据的平均大小是1K，那么一个数据页可以存放16行数据。
通常情况下，数据库使用B+树索引避免全表扫表数据库（目前，很多数据库引擎还支持其他类型的索引方式，如，全文索引、哈希索引）。
B+树索引基本原理：通过B+树搜索记录所在的页，然后通过把页读到内存，再在内存中查找到行数据。
Mysql中InnoDB的索引分为：
- 聚集索引：每张表的主键构成一棵B+树，叶子节点中存放整张表的行记录数据，即每一个叶子节点作为一个数据页，每个数据页之间通过一个双向链表进行链接，非数据页存放的是键值和指向数据页的偏移量，一张表只能有一个聚集索引。
- 辅助索引：按照每张表创建的索引列创建一棵B+树，叶子节点并不包含行记录的全部数据，只包含键值和bookmarks，bookmarks记录行数据的位置（通常bookmarks为行的主键值）。每张表可以有多个辅助索引。
B+ 树的高度¶
B+ 树的高度决定了一次查询需要进行的逻辑IO次数，假设：聚集索引的B+树高度为3， 辅助索引的 B+ 树高度为2，那么从主键查询发生3次逻辑IO，从辅助索引查询发生5次IO。
参考如何获取InnoDB树的高度和在环境上做的试验可以得到下面结论：
- InnoDB中索引树的高度是会变化的，空表聚集索引的树高为1，后续会逐渐上升；
- 获取当前树的高度可以使用文中提到的方式，一般情况下千万规模的表，树的高度大约是3左右；
- 聚集索引B+树中间节点阶数（能够容纳的元素数目）= innodb_page_size/(主键长度 + 6b)
- 聚集索引B+树叶子节点阶数（能够容纳的元素数目）= innodb_page_size/(Row的长度)
聚集索引存放的数据行数¶
假设一个数据页16K（innodb中取决于innodb_page_size配置），一条数据1K，即单个数据页能存放16条数据。
假设主键为bigint类型（8个字节），指针大小为6个字节，一个非子页节点能够存放16kb/14b=1170条记录。
如果聚集索引B+树的高度为3，那么存放记录数为：16*1170^m-1，当m=3时大概是2千万数据。