面试：常见数据结构
树相关
B树
B树（B-tree）是一种自平衡的树型数据结构，广泛应用于文件系统、数据库系统以及其他需要对大量数据进行快速查找、插入和删除操作的场景。B树的设计旨在优化对磁盘等外部存储设备的访问，通过减少磁盘I/O次数来提高效率。下面是B树的详细介绍：
基本概念
-
多路平衡查找树：与二叉树不同，B树的每个节点可以有多个子节点，具体数量由树的阶数（阶数表示节点最多可以有多少个子节点）决定。阶数的选择通常与磁盘块的大小相关联，目的是最大化每个磁盘I/O操作的数据传输量。
-
自平衡：B树在插入和删除操作后能够自动调整结构，保持数据的平衡分布，确保从根节点到任何叶子节点的路径长度大致相等，从而保证查找、插入和删除操作的时间复杂度为对数级别。
结构特点
-
节点结构：每个节点包括一个键值数组和一个子节点指针数组。键值数组中的元素是有序的，且每个键值与其相邻的子节点指针之间存在关联关系，即子节点中存储的键值范围位于其父节点键值的两个相邻键值之间。
-
叶子节点：所有叶子节点位于同一层，并且叶子节点可以包含实际的数据项或指向数据项的指针。在某些定义中，叶子节点也可以存储数据记录的指针或索引。
-
分支因子：每个节点的子节点数量有一个最大限制，称为分支因子（或阶数）。一个m阶的B树满足以下条件：
- 根节点至少有两个子节点（除非树只有一个节点）。
- 所有非根节点至少有⌈m/2⌉个子节点。
- 除根节点外，所有节点至多有m个子节点。
-
关键字和子树：每个节点中的关键字数量总是小于等于子节点数量，且每个关键字都对应于一个子树，关键字按升序排列。
操作特性
- 查找：从根节点开始，根据查找键与节点关键字比较，决定进入哪个子树，直到找到目标键或到达叶子节点。
- 插入：新键值被插入到叶子节点中，并可能触发节点的分裂，如果节点已满，则向上分裂并调整父节点，必要时甚至分裂根节点。
- 删除：删除操作可能导致节点合并或重新分配键值，同样需要维护树的平衡性，可能需要从兄弟节点借键或合并节点。
应用场景
- 文件系统：B树用于文件系统的目录索引，快速定位文件位置。
- 数据库索引：作为数据库管理系统中的索引结构，加速数据检索。
- 内存管理：在一些操作系统中用于虚拟内存管理的页面替换算法。
B树的设计充分考虑了外部存储设备的访问模式，通过减少磁盘I/O次数，极大地提高了数据访问效率，是处理大量数据时非常重要的数据结构。
B+树
B+树是B树的一个变种，专为文件系统、数据库索引等场景设计，优化了范围查询和读取效率。以下是B+树的详细说明：
基本概念
B+树是一种自平衡的多路搜索树，其设计目标在于提高对磁盘等外部存储设备的数据访问效率。它通过减少树的高度和提供连续的数据访问路径，优化了大量数据的存储和检索过程。
结构特点
-
节点结构：B+树的每个节点可以有多个子节点，具体数量取决于树的阶数（最大子节点数）。节点中包含一组有序的关键字和指向子节点的指针。
-
叶子节点与内部节点：
- 内部节点：仅存储关键字和指向子节点的指针，不存储实际数据。每个关键字对应两个子节点之间的值域，且关键字在内部节点中也是有序的。
- 叶子节点：所有实际的数据或指向数据的指针都存储在叶子节点中，并且叶子节点通过指针相连，形成了一个双向链表，使得范围查询变得非常高效。
-
自平衡：如同B树，B+树在插入和删除操作后能够自动调整结构，确保树的平衡，从而维持查找、插入和删除操作的高效性。
-
高度优化：由于数据只存储在叶子节点，并且每个节点可以容纳更多关键字（因为不需要存储数据），B+树相比B树通常具有更少的层数，这意味着在查找数据时需要的磁盘I/O操作更少。
操作特性
- 查找：从根节点开始，根据查找键与节点关键字比较，递归向下遍历，直到到达叶子节点，然后在叶子节点的链表中进行线性查找。
- 插入：新数据插入到叶子节点，如果叶子节点满，则分裂节点，并可能引起父节点的分裂，直至根节点，必要时分裂根节点。
- 删除：删除操作可能导致叶子节点合并，如果节点变空，则需调整父节点，可能引起连锁反应直至根节点。
应用场景
- 数据库索引：B+树是数据库系统中常用的索引结构，特别适合于范围查询和排序操作。
- 文件系统：用于文件的快速定位，特别是在大型文件系统中。
- 缓存系统：在某些缓存或内存管理策略中，B+树用于高效地管理大量条目。
优点
- 读取效率高：由于数据集中存储在叶子节点，并且叶子节点通过指针相连，使得范围查询和顺序访问变得非常迅速。
- 较低的树高度：使得数据访问所需的磁盘I/O操作更少，提高了整体性能。
- 稳定性：B+树的自平衡特性确保了在动态数据集上也能保持高效。
综上所述，B+树以其高度的优化、高效的范围查询能力和对磁盘I/O的有效利用，在处理大量数据的存储和检索场景中表现出色。
B树和B+树的区别
B树和B+树都是自平衡的树数据结构，常用于数据库和文件系统中以提高磁盘访问效率。尽管它们有相似之处，但B+树作为B树的一个变种，在几个关键方面有所不同：
-
数据存储位置：
- B树：在B树中，数据既存储在内部节点（非叶子节点）也存储在叶子节点中。每个节点都可以包含数据项和指向子节点的指针。
- B+树：B+树中，只有叶子节点才真正存储数据（或指向数据的指针），而内部节点仅存储键值作为索引，并不存储实际数据内容。这使得B+树的内部节点可以存放更多的键值，从而减小了树的高度。
-
叶子节点结构：
- B树：叶子节点可以包含数据，并且叶子节点并不一定相互连接。
- B+树：所有叶子节点包含了全部的数据项，并且这些叶子节点通过指针相连，形成一个有序的链表，便于范围查询。
-
查询效率：
- B树：由于内部节点也可能包含数据，查询时可能在内部节点就找到所需数据，但这也意味着查询路径不固定。
- B+树：所有查询最终都会到达叶子节点，因此查询路径长度固定，查询效率更为稳定。特别是对于范围查询，由于叶子节点间有指针相连，可以非常高效地遍历。
-
磁盘读写效率：
- B+树通常被认为在磁盘读写上更高效，因为它允许更多的键值存储在每个节点中（因为内部节点不存储数据），减少了树的高度，从而减少了磁盘I/O次数。
-
应用场景：
- B树因其在内部节点也可以快速定位数据的特性，适用于某些需要快速查找单个元素的场景。
- B+树由于其叶子节点的链表结构和高度的优化，更适合用于数据库索引和文件系统，尤其是需要大量范围查询和全表扫描的情况。
综上所述，B+树在数据库索引中更为常见，因为它在提高查询效率、尤其是范围查询和大规模数据存储方面具有优势。而B树在某些特定场景下，如需要在内部节点直接访问数据时，也有其应用价值。