B+树（B树的改进）
目录
一、什么是B+树？
二、B+树的性质
1.B+树被广泛作为数据库索引的索引结构
2.m个分支的结点有m个元素
3.每个元素对应子结点最大值
4.多级索引结构
5.叶子结点层包含所有元素
三、B树和B+树的区别
四、B+树的查找
1.顺序查找
2.随机查找
3.范围查找
一、什么是B+树？
B+树是一种改进自B树的数据结构,它可以在数据文件中快速地查找数据,也可以通过多级索引结构加速查询速度。
B+树的每个叶子节点都包含关键字和对应的记录指针,而非叶子节点则用于快速定位关键字。
B+树可以进行顺序查找和随机查找,同时还可以结合两者进行范围查找。它是一种常用于数据库索引的数据结构。
二、B+树的性质
1.B+树被广泛作为数据库索引的索引结构
2.m个分支的结点有m个元素
3.每个元素对应子结点最大值
4.多级索引结构
只有叶子结点的关键字才存储着指向数据记录的指针，
叶子结点的上一层非叶子结点是对叶子结点的索引，
上次层是对下一层的索引。
5.叶子结点层包含所有元素
三、B树和B+树的区别
| B树所有结点的关键字都有直接指向对应记录的指针 | B+树叶结点包含全部关键字及指向相应记录的指针,非叶结点只作索引 |
| B树中m个分支有m-1个关键字 | B+树中m个分支有m个关键字 |
| B树顺序查找或范围查找只能中序遍历,效率低 | B+树兼顾顺序查找和随机查找，还可方便地进行范围查找 |
四、B+树的查找
1.顺序查找
由于叶子结点层包含所有B+树的所有元素，并且用链表链接在一起，所以直接可以从叶子结点的链表头Head开始顺序查找。
2.随机查找
①先从root指针找到根结点和根节点的元素进行比较，比某元素小走某元素的子树，若大于继续向右进行比较；
②如果找到对应元素时不是叶子结点，该关键字没有存储记录的指针，还要继续上述步骤往下走，直到找到叶子结点。
意思说，B+树的查找最后一定会落到叶子结点。
3.范围查找
根据随机查找的方式找到范围在叶子结点层链表的起点，接着在列表中往后顺序查找。
