数据库索引与哈希技术详解

# 数据库索引与哈希技术详解 在数据库管理中，索引和哈希技术是提高数据查询效率的重要手段。下面将详细介绍B树与B+树、闪存存储、多键访问以及静态哈希等相关内容。 ## 1. B树与B+树的比较 B树和B+树是数据库中常用的索引结构。与B+树相比，B树的非叶节点中出现的搜索键较少，这意味着B树的扇出较小，深度可能比对应的B+树更大。因此，B树对于某些搜索键的查找速度较快，但对于其他搜索键则较慢，不过总体而言，查找时间仍然与搜索键的数量的对数成正比。 在删除操作方面，B+树中被删除的条目总是出现在叶子节点，而B树中被删除的条目可能出现在非叶节点。此时，必须从包含被删除条目的节点的子树中选择一个合适的值作为替换。具体来说，如果删除搜索键Ki，则必须将指针Pi + 1的子树中出现的最小搜索键移动到Ki原来占用的字段中。如果叶子节点现在的条目太少，则需要采取进一步的操作。而在插入操作上，B树仅比B+树稍微复杂一些。 对于大型索引，B树的空间优势并不明显，通常无法弥补其缺点。因此，几乎所有的数据库系统实现都使用B+树数据结构，即使它们可能将其称为B树。 ## 2. 闪存存储对索引结构的影响 在之前的索引描述中，我们假设数据存储在磁盘上。然而，闪存的容量显著增加，每GB的成本也大幅下降，使得闪存存储成为许多应用中替代磁盘存储的有力竞争者。那么，这种变化会如何影响索引结构呢？ 闪存存储以块为结构，B+树索引结构可以用于闪存存储。闪存的快速访问速度对于索引查找非常有利，随机块的读取时间约为1微秒，而磁盘平均需要10毫秒。因此，与基于磁盘的数据相比，查找速度显著加快。此外，闪存的最佳B+树节点大小通常比磁盘小。 不过，闪存的一个缺点是它不允许在物理层面进行原地数据更新，尽管在逻辑上看起来可以。每次更新都需要复制并写入整个闪存块，随后需要擦除旧的块副本，擦除一个块大约需要1毫秒。目前有研究致力于开发能够减少块擦除次数的索引结构。同时，标准的B+树索引即使在闪存存储上也可以继续使用，更新性能可以接受，并且与磁盘存储相比，查找性能有显著提高。 ## 3. 多键访问 ### 3.1 使用多个单键索引 假设教师文件有两个索引：一个是部门名称索引，另一个是工资索引。考虑以下查询：“查找所有在财务部门且工资为80,000美元的教师”。可以使用以下SQL语句表示： ```sql select ID from instructor where dept_name = 'Finance' and salary = 80000; ``` 处理此查询有三种可能的策略： 1. 使用部门名称索引查找所有与财务部门相关的记录，然后检查每个记录的工资是否为80,000美元。 2. 使用工资索引查找所有工资为80,000美元的教师记录，然后检查每个记录的部门名称是否为“Finance”。 3. 使用部门名称索引查找所有与财务部门相关的记录的指针，同时使用工资索引查找所有工资为80,000美元的教师记录的指针，然后取这两组指针的交集。交集中的指针指向的记录即为在财务部门且工资为80,000美元的教师记录。 第三种策略是唯一利用多个索引的策略，但如果满足以下所有条件，该策略可能不是一个好选择： - 与财务部门相关的记录很多。 - 工资为80,000美元的教师记录很多。 - 同时属于财务部门且工资为80,000美元的教师记录很少。 在这种情况下，需要扫描大量的指针才能得到少量的结果。一种称为“位图索引”的索引结构在某些情况下可以大大加快第三种策略中使用的交集操作。 ### 3.2 多键索引 另一种策略是创建并使用复合搜索键（部门名称，工资）的索引。可以使用有序（B+树）索引来高效地回答以下形式的查询： ```sql select ID from instructor where dept_name = 'Finance' and salary = 80000; ``` 对于指定搜索键的第一个属性（部门名称）为相等条件，第二个属性（工资）为范围条件的查询，也可以高效处理，因为它们对应于搜索属性上的范围查询。例如： ```sql select ID from instructor where dept_name = 'Finance' and salary < 80000; ``` 甚至可以使用搜索键（部门名称，工资）的有序索引来高效地回答仅针对一个属性的查询： ```sql select ID from instructor where dept_name = 'Finance'; ```