B 树索引

如索引基础概念页面中介绍的，SmartEDB 的 B 树（树）索引可以包含来自给定类的任意组合的字段、结构元素或向量元素。树索引可用于有序（排序）检索、范围检索和模式匹配。此外，键值包含索引和覆盖索引可与树形索引结合使用，通过在索引中包含所需的数据字段来显著提高性能。

键值包含索引和覆盖索引

SmartEDB 内存数据库的实现最初是在随机存取设备占据主导地位的 RAM 内存时期创建的；也就是说，访问内存中的任何位置所花费的时间和 CPU 周期都相同。这种模型在最近几年之前对于嵌入式设备以及服务器型架构都是准确的。CPU 速度慢且 RAM 容量小，直接读写 RAM 并不会造成明显的瓶颈。然而，近年来，即便是普通的台式机 CPU 也具备了深度缓存层次结构——至少有一个相当大的 L1 和 L2 缓存——以防止 CPU 被 RAM 访问所支配。CPU 缓存的访问速度比普通 RAM 快得多（快一个数量级或更多）。能够有效利用 CPU 缓存的数据结构和算法，其执行速度要比那些不能有效利用缓存的算法快得多。此外，如今在多处理系统中，大型内存访问算法几乎总是通过 NUMA 内存架构来实现，这为数据和索引优化带来了其他性能优势和挑战。

键值包含索引

SmartEDB 为内存（临时）数据库类提供了一种“键值包含”或“缓存无关”的实现方式，这能加快某些访问模式的访问速度。特别是针对非常大的 B 树索引进行的实验表明性能有显著提升。此外，三元组索引是通过“键值包含”树实现的，因为将 3 个额外字节（三元组）保存在索引页上要比仅仅存储一个 8 字节的对象地址更高效，后者需要进一步的访问步骤。

请注意，Java、C# 和 Python 的 API 目前不支持包含索引。

覆盖索引

如果索引搜索中请求的所有字段都在索引中可用，那么运行时就无需再次查找索引所覆盖的对象。这可以显著提高搜索性能。由于所有请求的字段都在索引中可用，因此该索引被称为“覆盖索引”。

内存消耗

对于瞬态类的树索引和哈希索引，内存消耗是相当的。树索引的粗略估计是每个条目 10 字节（确切大小取决于插入或删除的顺序）；哈希索引则是每个条目 H + 8 字节，其中常量 H 是哈希表所占用的固定大小空间，可按您在数据库模式中提供的哈希条目估计数 E 除以 5 再乘以 4 来计算，5 是 SmartEDB 所使用的常量哈希因子。如果需要重新分配哈希表，则大小将是 H * 2。