b+tree图示
b+tree的核心特点
b+树是b树的一种变体，它在数据库索引中更为常见。与b树相比，b+树有以下关键区别： 1、内部节点只存键，不存数据：所有数据都存储在叶子节点中。内部节点仅用于索引，即指引搜索方向。 2、叶子节点形成有序链表：所有叶子节点通过指针连接在一起，形成一个有序链表，便于范围查询。 b+树结构： 内部节点（索引节点）： 存储键值（用于导航）和子节点指针。 键值个数比子节点指针个数少1个（和b树一样）。 键值按照升序排列。 叶子节点（数据节点）： 存储键值和对应的数据（或指向数据的指针）。 键值按照升序排列。 有指向下一个叶子节点的指针，形成有序链表。 树的高度平衡： 和B树一样，b+树也是高度平衡的，所有叶子节点在同一层。b+tree的优势
1、更高的扇出：由于内部节点只存储键，不存储数据，所有每个内部节点可以存储更多的键，从而降低树的高度，减少磁盘i/o次数。 2、范围查询高效：叶子节点形成有序链表，只需要找到第一个键，然后沿着俩表遍历即可。 3、全表扫描更高效：只需要遍历叶子节点链表，而不需要遍历整棵树 4、数据全部在叶子节点：查询性能稳定（每次查询都要到叶子节点）。b+tree的操作
1、查找 （1）、从根节点开始，根据键值在内部节点中找出合适的子节点指针，直到叶子节点。 （2）、在叶子节点中查找键值，如果找到则返回数据（或指针）。 2、插入 （1）、插入操作可能会引起节点的分裂。分裂方式与B树类似，但有一些不同： Ⅰ、找到要插入的叶子节点。 Ⅱ、如果叶子节点未满，直接插入并保持有序。 Ⅲ、如果叶子节点已满，则分裂叶子节点： - 将原节点中的键值和新键值排序，分成两个节点，每个节点包含一半的键值。 - 将中间简直复制到父节点中（b树是移动中间键值到父节点，而b+树是复制）。 - 如果父节点也满了，则递归分裂父节点。 3、删除 （1）、找到要删除的键值所在的叶子节点。 （2）、从叶子节点中删除键值。 （3）、如果删除后叶子节点的键值数值低于最小要求（即半满），则需要合并或从兄弟节点借键值。 Ⅰ、如果兄弟节点有富余，则从兄弟节点借一个键值，并更新父节点中的键值。 Ⅱ、如果系统地节点没有富余，则合并两个叶子节点，并删除父节点中对应的键值。 注意：删除内部节点中的键值时，需要保证树仍然能够正确导航。在b+树中，内部节点的键值指示用于盗汗给，所以删除叶子节点中的见之后，如果这个键值在内部节点中出现，通常需要保留（除非它不再需要）。实际上，b+树的删除操作比B树简单，因为数据只在叶子节点，内部节点的键值只是副本。b+树在数据库中的应用
在关系型数据库（如mysql的innoDB引擎）中，主键索引就是聚簇索引，它使用b+树组织数据。二级索引也是用b+树，但叶子节点存储的是主键值。 1、聚簇索引（主键索引） 叶子节点存储的是整行数据。 表数据本身就是按照主键顺序存储的（即索引组织表）。 2、二级索引（非聚簇索引） 叶子节点存储的是主键值，而不是整行数据。 通过二级索引查找数据时，需要先找到主键，然后通过主键索引找到整行数据（即回表）b+树总结
b+树通过将数据全部存储在叶子节点，内部节点仅存储键，提高了扇出，降低了树高，从而减少了磁盘i/o次数。同时，叶子节点形成有序列表，使得范围查询和全表扫描非常高效。因此，B+树称为数据库索引的首选数据结构。在实际的数据库系统中，b+树还会结合一些优化技术，如预读、缓存、压缩等，以进一步提升性能。
