索引习题记录

1. 索引可以加快查询处理速度，但为每个属性以及每个属性组合（这些属性是潜在的搜索键）创建索引通常不是一个好主意。解释为什么。
   答：每个额外的索引都需要额外的存储空间；每个索引都需要在插入和删除时额外的CPU时间和磁盘I/O开销；如果有 $n$ 个属性，那么需要 $2^n$ 个索引，这是指数级的。
2. 一般来说，对于不同的搜索键，是否可以在同一关系上有两个聚簇索引？解释你的答案。
   答：不可以。聚簇索引是按照索引键对数据行进行排序和存储的。因此，每个表只能有一个聚簇索引，因为数据行本身只能按照一种顺序存储。如果有两个聚集索引，那么每个数据行都需要存储两次，每个索引都要存一次，这会浪费存储空间。
3. 如果索引条目按排序顺序插入，B±树的每个叶节点的占用率是多少？解释为什么。
   答：如果索引项按照排序顺序插入B+树，那么每次插入导致一个叶节点满了，都会分裂成两个新的叶节点，每个包含一半条目。因此，每个叶节点的占用率是 50%。
4. 假设有一个包含 $n_r$ 个元组的关系 $r$，要在该关系上构建辅助 B+树。
   a. 给出一次插入一条记录来构建 B+ 树索引的成本的公式。假设每个块平均保存 $f$ 个条目，并且叶子上方的树的所有级别都在内存中。
   b. 假设随机磁盘访问需要 10 毫秒，那么针对 1000 万条记录的关系构建索引的成本是多少？
   c. 编写伪代码以自下而上构建 B+ 树。可以假设有一个可以对大文件进行有效排序的函数。
   答：
   a. $C=n_r\cdot (1+{\log }_f{n}_r)/f\ast t$
   b. $C=1000000\cdot (1+lo{g}_{f}1000000)/f\cdot 0.01$
   c.

# 假设有一个函数sort_file(file, key)可以对一个大文件按照给定的键进行排序
# 假设有一个函数split_node(node)可以将一个满节点分裂成两个节点，并返回中间键和新节点的指针
# 假设有一个函数insert_entry(node, entry)可以将一个条目插入到一个节点中，并处理溢出情况
# 假设有一个函数create_node(entries)可以创建一个新节点，并用给定的条目填充它
# 假设有一个函数read_block(file, offset)可以从一个文件中读取一个块的内容
# 假设有一个函数write_block(file, offset, content)可以向一个文件中写入一个块的内容
# 假设有一个常量BLOCK_SIZE表示块的大小
# 假设有一个常量MAX_ENTRIES表示每个节点能够容纳的最大条目数

def build_b_plus_tree(file, key):
  # 对文件按照键进行排序
  sort_file(file, key)
  # 初始化根节点为空
  root = None
  # 初始化当前层的节点列表为空
  current_level = []
  # 初始化下一层的节点列表为空
  next_level = []
  # 初始化文件偏移量为0
  offset = 0
  # 循环直到文件结束或者根节点创建
  while not file.eof() or not root:
    # 如果当前层为空，说明刚开始或者刚完成一层的处理
    if not current_level:
      # 如果下一层只有一个节点，说明它就是根节点
      if len(next_level) == 1:
        root = next_level[0]
        break
      # 否则，把下一层赋值给当前层，并清空下一层
      else:
        current_level = next_level
        next_level = []
    # 如果当前层不为空，取出第一个节点
    else:
      node = current_level.pop(0)
    # 读取一个块的内容，作为数据条目
    entries = read_block(file, offset)
    # 如果数据条目为空，说明文件结束，跳出循环
    if not entries:
      break
    # 如果节点是叶子节点，直接将数据条目插入到节点中
    if node.is_leaf():
      for entry in entries:
        insert_entry(node, entry)
    # 如果节点是非叶子节点，创建一个新的叶子节点，并用数据条目填充它
    else:
      new_node = create_node(entries)
      new_node.set_leaf(True)
      # 将新节点的第一个条目的键作为索引条目，插入到当前节点中，并指向新节点
      index_entry = (new_node.get_first_key(), new_node)
      insert_entry(node, index_entry)
    # 如果当前节点已满，将它分裂，并将中间键和新节点的指针插入到下一层的第一个节点中
    # 如果下一层为空，创建一个新的节点作为下一层的第一个节点
    if node.is_full():
      middle_key, new_node = split_node(node)
      if not next_level:
        next_level.append(create_node([]))
      insert_entry(next_level[0], (middle_key, new_node))
    # 更新文件偏移量
    offset += BLOCK_SIZE
  # 返回根节点
  return root

5. B+树文件组织的叶节点在一系列插入后可能会丢失顺序。
   a. 解释为什么顺序可能会丢失。
   b. 为了最大限度地减少顺序扫描中的查找次数，对于某些相当大的 $n$，许多数据库在 $n$ 个块的范围内分配叶页。当分配 B+ 树的第一个叶子时，仅使用 $n$ 块单元中的一个块，其余页是空闲的。如果页面分裂，并且其 $n$ 块单元有一个空闲页面，则该空间将用于新页面。如果 $n$ 块单元已满，则分配另一个 $n$ 块单元，并且前 $n∕2$ 叶页放置在一个 $n$ 块单元中，剩余的放置在第二个 $n$ 块单元中。为简单起见，假设没有删除操作。
   i. 假设第一个 $n$ 块单元已满后，最坏情况下分配空间的占用情况是多少？
   ii. 是否有可能分配给一个 $n$ 节点块单元的叶子节点不是连续的，即是否有可能两个叶子节点分配给一个 $n$ 节点块，但两者之间的另一个叶子节点分配给不同的 $n$ 节点块？
   iii. 在缓冲区空间足以存储 $n$ 页块的合理假设下，在最坏的情况下，B+ 树的叶级扫描需要多少次查找？如果一次分配一个叶页块，将此数字与最坏情况进行比较。
   iv. 当与前面的叶块分配方案一起使用时，将值重新分配给兄弟节点以提高空间利用率的技术可能会更有效。解释为什么。
   答：a. 叶子节点的顺序性可能会丢失的原因是，当插入一个新的数据条目时，可能会导致叶子节点分裂。分裂后，原来的叶子节点和新的叶子节点之间的指针可能会指向不连续的物理块，从而破坏了顺序性。
   b.
   i. 最坏情况占用率是 $50\%$。这是因为当第一个 $n$ 块单元满了之后，需要分配一个新的单元，并将前 $n/2$ 个叶子页面移到新的单元中。这样，原来的单元就只剩下 $n/2$ 个叶子页面，而新的单元也只有 $n/2$ 个叶子页面。所以，两个单元中一共有 $n$ 个叶子页面，占用了 $2n$ 个块，占用率是 $50\%$。
   ii. 不可能。这是因为当一个页面分裂时，它会优先使用它所在的单元中的空闲页面。只有当这个单元已经满了时，才会分配一个新的单元，并将 $n/2$ 个叶子页面移到新的单元中。这样，每个单元中的叶子节点都是连续的，并且按照键值排序。
   iii. 在最坏情况下，需要 $\lceil \frac{N}{n}\rceil$ 次寻道来进行B+树的叶级扫描，其中 $N$ 是B+树中数据条目的总数。这是因为每次寻道可以读取一个 $n$ 页块，并且每个 $n$ 页块都至少有 $\lceil \frac{n}{2}\rceil$ 个数据条目。所以，总共需要 $\lceil \frac{N}{\lceil \frac{n}{2}\rceil }\rceil =\lceil \frac{N}{n}$⌉次寻道。与每次分配一个块的叶页面相比，这个数字要小得多。如果每次分配一个块的叶页面，那么在最坏情况下，需要 $N$ 次寻道来进行B+树的叶级扫描，因为每次寻道只能读取一个数据条目。所以，使用 $n$ 块单元的分配方法可以显著减少寻道次数。
   iv. 这是因为当使用前面描述的分配叶块的方法时，每个单元中的叶节点都是连续的，并且按照键值排序。这样，当一个叶节点的数据条目过少时，可以从它相邻的兄弟节点中借用一些数据条目，而不需要改变它们所在的单元。这样就可以避免分裂和合并操作，从而提高空间利用率和性能。
6. 假设给你一个数据库模式和一些频繁执行的查询。你将如何使用上述信息来决定创建哪些索引？
   答：
   分析查询的执行计划，找出那些需要优化的查询，比如扫描了过多的行或者进行了过多的I/O操作的查询。
   根据查询中涉及的表、列、谓词、排序和聚合等因素，确定可能的索引候选。一般来说，有以下几种情况可以考虑创建索引：表中有大量的数据，并且经常根据某些列进行筛选、排序或者聚合的操作。表中有作为外键的列，并且经常与其他表进行连接操作。表中有唯一性约束或者主键约束的列，或者需要保证数据完整性的列。表中有需要支持全文搜索或者空间搜索的列。
   根据不同类型的索引的特点和限制，选择合适的索引类型。例如，如果表是基于行存储的，可以选择聚集索引、非聚集索引、唯一索引、过滤索引等；如果表是基于列存储的，可以选择列存储索引；如果表是基于内存优化的，可以选择哈希索引或者内存优化非聚集索引等。
   根据索引类型和候选列，设计索引的结构和属性。例如，确定索引包含哪些列，以及列的顺序；确定索引是否包含其他非键列；确定索引是否是升序还是降序；确定索引是否有过滤条件等。
   在创建索引之前，评估索引对查询性能和空间占用的影响。可以使用数据库提供的工具或者命令来模拟创建索引后的查询执行计划和统计信息，比如SQL Server中的Database Engine Tuning Advisor或者sys.dm_db_index_physical_stats函数等。
   在创建索引后，监控索引的使用情况和维护情况。可以使用数据库提供的工具或者命令来查看索引是否被查询优化器使用，以及索引是否有碎片或者过期等问题，比如SQL Server中的sys.dm_db_index_usage_stats函数或者sys.dm_db_index_operational_stats函数等。
   根据监控结果，调整或者删除不必要或者低效的索引。例如，如果一个索引很少被使用，或者与另一个索引重复，或者对更新操作造成很大开销，那么可以考虑删除这个索引。
7. 在写优化树（例如 LSM 树或步进合并索引）中，只有当该级别已满时，一级中的条目才会合并到下一级。建议如何更改此策略以在有大量读取但没有更新的期间提高读取性能。
   答：
   在每个层级之间增加一个缓冲区（buffer），用于存储待合并的条目。这样，当读取一个层级时，可以先检查缓冲区中是否有更新的条目，从而减少对下一层级的访问。
   在每个层级之间增加一个布隆过滤器（bloom filter），用于记录每个层级中包含的键值范围。这样，当读取一个层级时，可以先检查布隆过滤器中是否有匹配的键值，从而避免不必要的访问。
   在每个层级之间增加一个索引（index），用于指向每个层级中的数据块。这样，当读取一个层级时，可以通过索引快速定位到包含目标键值的数据块，从而减少扫描的开销。
   在空闲时间或者后台线程中，主动触发合并操作（merge），将上一层级中的条目合并到下一层级中。这样，可以减少每个层级中的数据量，从而提高读性能。
8. 与 LSM 树相比，缓冲树有哪些权衡？
   答：
   读效率：与LSM树相比，Buffer树通常提供更好的读效率。由于Buffer树将数据存储在排序结构（如B+树）中，可以通过高效的树遍历算法快速定位和检索特定数据。
   写效率：与LSM树相比，Buffer树的写入性能可能较慢。每个写操作都涉及更新树结构，当处理大量写操作时，这可能会导致开销较大。但是，一些优化技术如写入缓冲和批量加载可以帮助缓解这个问题。
   内存使用：Buffer树需要足够的内存来容纳整个索引结构，包括内部节点和叶节点。当处理大型数据集或可用内存有限时，这可能是一个限制因素。
   立即索引：Buffer树提供立即索引，即数据插入后立即可供读取。无需进行额外的后台压缩或合并过程，适用于需要实时或低延迟访问数据的场景。
9. 什么时候最好使用密集索引而不是稀疏索引？
   答： 一般来说，当需要快速查询数据时，使用密集索引比稀疏索引更好。密集索引是指为表中的每一行数据都建立一个索引项，而稀疏索引是指只为表中的部分数据或每个数据块建立一个索引项。密集索引可以直接定位到数据，而稀疏索引需要先找到对应的数据块，然后再在数据块中搜索数据。但是，密集索引也有一些缺点，比如占用更多的空间，以及在插入、更新或删除数据时需要更多的维护工作。另外，密集索引不需要表中的数据按照索引列值排序，而稀疏索引则需要。所以，具体使用哪种索引要根据实际情况和需求来决定。如果查询操作比较频繁，而更新操作比较少，那么密集索引可能更合适。如果表中的数据很大，而且已经按照索引列值排序，那么稀疏索引可能更节省空间和维护成本。
10. 假设必须在大量名称上创建 B+ 树索引，其中名称的最大大小可能相当大（例如 40 个字符），而平均名称本身也很大（例如 10 个字符）。解释如何使用前缀压缩来最大化非叶节点的平均扇出。
    答：对于每个名称，在构建B+树索引之前，根据名称的长度将其分为多个前缀。在非叶节点中存储这些前缀而不是完整的名称。这样可以大大减小非叶节点的大小。在非叶节点上的键值对中，除了存储前缀外，还存储指向对应子节点的指针。在进行索引查询时，根据需要，将查询键值与非叶节点上的前缀进行比较，以确定下一步要搜索的子节点。
11. 假设一个关系存储在一个B+树文件组织中。假设二级索引存储记录标识符，它们是指向磁盘上记录的指针。
    a. 如果在文件组织中发生了节点分裂，会对二级索引有什么影响？
    b. 更新二级索引中所有受影响的记录的代价是多少？
    c. 如何使用文件组织的搜索键作为逻辑记录标识符来解决这个问题？
    d. 使用这样的逻辑记录标识符会带来额外的成本吗？
    答：
    a. 如果在文件组织中发生了节点分裂，会导致辅助索引中的一些记录标识符失效，因为它们指向的记录可能已经被移动到新的节点中。这就需要更新二级索引中所有包含失效指针的数据项。
    b. 更新二级索引中所有受影响的记录的代价取决于分裂节点中有多少记录被移动，以及二级索引中有多少数据项引用了这些记录。如果分裂节点中有 $n$ 个记录被移动，而每个记录在二级索引中有 $m$ 个数据项引用它，那么总共需要更新 $nm$ 个数据项。每个数据项的更新代价包括查找、删除和插入操作。如果二级索引也是B+树结构，那么每个操作的平均代价是 $O({\log }_{B}N)$，其中 $B$ 是B+树的分支数，$N$ 是B+树的数据项数。因此，总的更新代价是$O(nm{\log }_{B}N)$。
    c. 使用文件组织的搜索键作为逻辑记录标识符可以解决这个问题，因为这样就不需要存储指向磁盘上记录的物理指针，而是存储能够唯一标识记录的搜索键值。这样，即使文件组织中发生了节点分裂，也不会影响二级索引中的数据项，因为它们仍然可以通过搜索键找到对应的记录。
    d. 使用这样的逻辑记录标识符会带来额外的成本，因为它们通常比物理指针占用更多的空间，从而增加了二级索引的大小和存储需求。此外，使用逻辑记录标识符还需要在文件组织中进行额外的查找操作，以便根据搜索键找到对应的记录。这可能会增加查询性能的开销。
12. 与 B+ 树索引相比，写优化索引有何权衡？
    答：写优化的索引通常需要更多的空间来存储，因为它们通常有重复的数据。此外，写优化的索引往往更复杂，因此更难管理和更新。写优化的索引的优点是它们可以减少对非易失性内存（NVM）或固态硬盘（SSD）等新型存储设备的写操作，从而提高写性能和延长设备寿命。这些设备的写操作通常比读操作更耗时和更昂贵，因此需要采用一些技术来减少写放大和保证数据持久性和一致性。一些写优化的索引的例子包括WB-tree、Fast&Fair、FPtree和WO-tree，它们都是基于B+树的变体，但采用了不同的方法来减少对NVM或SSD的写操作。例如，WB-tree使用无序的叶子节点来避免维护条目顺序所带来的写操作；Fast&Fair使用一个平衡因子来控制节点分裂和合并的频率；FPtree使用指纹技术来压缩索引键；WO-tree使用两层结构来分别优化读和写性能。
13. 存在位图是一种用于表示记录是否存在的位图，它对每个记录位置有一个位，如果记录存在，则该位设置为1，如果该位置没有记录（例如，如果记录被删除），则该位设置为0。请展示如何从其他位图计算存在位图。确保你的技术即使在存在空值的情况下也能工作，通过使用一个表示空值的位图。
    答：假设我们有一个或多个属性位图，它们对每个记录位置有一个位，表示该记录的某个属性是否具有某个值。例如，如果我们有一个性别属性，它可以是男或女，那么我们可以有两个属性位图，一个表示性别为男，另一个表示性别为女。如果一个记录的性别属性为空值，那么这两个属性位图中对应的位置都是0。我们还可以有一个空值位图，它对每个记录位置有一个位，表示该记录是否具有空值。要从这些属性位图和空值位图计算存在位图，我们可以使用逻辑或运算。我们可以将所有的属性位图进行逻辑或运算，得到一个结果位图，它表示每个记录位置是否具有属性值。然后我们可以将这个结果位图和空值位图进行逻辑或运算，得到最终的存在位图，它表示每个记录位置是否存在任何记录。例如，假设我们有以下三个属性位图和一个空值位图：
    性别为男： 10010110
    性别为女： 01101001
    空值： 00000010
    将三个属性位图进行逻辑或运算得到：
    10011111
    将这个结果和空值位图进行逻辑或运算得到：
    10011111
    这就是存在位图。
14. 一些关系的属性可能包含敏感数据，可能需要以加密的方式存储。数据加密如何影响索引方案？特别是，它如何影响试图按排序顺序存储数据的方案？
    答：数据加密会影响索引方案的设计和性能，因为它会限制对数据的访问和操作。特别是，如果使用传统的加密方法，如对称加密或非对称加密，那么加密后的数据将无法保持原始数据的顺序，从而导致无法使用基于排序的索引方案，如B树或B+树。
    为了在加密数据上实现排序查询，有两种可能的解决方案。一种是使用顺序保持加密（OPE）方案，它是一种特殊的加密方法，可以保证加密后的数据与原始数据具有相同的顺序关系 。这样就可以在加密数据上使用基于排序的索引方案，如B+树或优先R树。但是，OPE方案也有一些缺点，如泄露数据的顺序信息、难以支持动态更新和多属性查询等。
    另一种是使用基于哈希或指纹的索引方案，它是一种不依赖于数据顺序的索引方法，可以在任意加密数据上使用 。这样就可以避免泄露数据的顺序信息，并且更容易支持动态更新和多属性查询。但是，基于哈希或指纹的索引方案也有一些缺点，如增加了存储空间和计算开销、降低了查询效率和精度等 。