【数据结构】动态查找表
动态查找表
动态查找表，表结构本身是在查找过程中动态生成的，动态更新意味着适合使用指针
二叉排序树
二叉排序树：构造的过程就是排序的过程，在无序的关键字序列中，在既有的二叉排序树（一开始的二叉排序树是一个空树）中查询一个个关键字应该所在的位置，往二叉排序树一个个添加，最后只需要对生成的二叉排序树进行中序遍历就可以得到有序的关键字序列了
在实际应用中，平衡二叉树有其弊端——在数据量大的情况下深度太大，因为每当访问一个节点的时候，我们需要进行更多的比较（每层都要比较选择进入哪个子树），不过消耗时间主要不是在内存中元素之间的比较，而是每次进入一个节点时都需要进行磁盘I/O读取，那么为了减少时间消耗，我们现在需要的就是尽量减少树的深度，引入B-树这种数据结构
B-树
B-树要尽量减少树的深度，为了达到这个目的，B-树增加了可拥有子节点的上限；还有要提高每个节点的利用率（不要存储太少的元素），设置一个下限，每个节点的子节点（M个）保持在 (m/2)-1(向上取整）<= M <= m 之间，下限取m/2（向上取整）-1是考虑到节点之间的合并操作，低于m/2才能进行合并操作，合并时候是两个子节点（一个(m/2)-2和一个(m/2)-1）和父节点的一个元素合并，也就是说合并后的节点会不会超过上限；还有要保证所有叶子节点不要参差不齐，保持在同一层，这也有利于树深度的降低
初步接触B-树这种数据结构，直觉来看相较于平衡二叉树那种明显严密的结构更加杂乱，特别是在动态更新中元素的插入和删除，元素的插入和删除会分很多种情况，每种情况都会有相应的处理方式，而且相较于平衡二叉树的变化，B-树的变化更加复杂，有时候会牵一发动全身，一个元素的增删可能会引起很大的结构变化，不过剖析每种情况后也对其严密的逻辑有了相对直观的认识，B-树是一种和平衡二叉树差不多的分叉更多而深度更小的数据结构，虽然B-树的查找过程中比较次数并不比平衡二叉树少，但访问节点次数少了很多，节省了时间消耗
B+树
B+树是在B-树基础上进一步改进，结构、动态变化方式和B-树基本相同，不同的是B+树拥有k个子树的节点拥有k个元素，而且中间节点的元素仅包含指向子树的指针，不包含指向数据的指针，也就是说，中间节点不包含卫星数据（指针指向的数据记录），叶子节点包含了所有数据。精简了中间节点，使得同一磁盘页可以包含更多的元素，也就是可以更多分叉，进一步降低树的深度，降低查询时IO次数；同时相较于B-树，B+树的每次查询都需要从根节点出发一直到达叶子节点完成一次查询，这使得每次查询消耗时间更加稳定；还有就是B+树的所有叶子节点通过指针链接起来，形成一条有序链表，这有利于对元素进行顺序遍历（B-树中的遍历需要通过中序遍历实现），以及有利于进行数据库中的常用操作——范围查找（从数据集中查询满足特定范围条件的数据）。
参考链接
https://wardseptember.github.io/notes/#/docs/B%E6%A0%91%E5%92%8CB+%E6%A0%91%E8%AF%A6%E8%A7%A3