从检索的角度聊聊数据结构的演进

        如何高效地存取和检索这些数据，是数据结构演进的核心驱动力，而所有的数据结构，其实都是最基础的​​数组​​和​​链表​​两者的结合和变化。

一、基础结构：数组与链表​

1. 数组 (Array)​

• ​​特点​​：使用一块​​连续的内存空间​​来存储相同类型的数据。这种“连续空间存储”带来了一个至关重要的特性：​​随机访问 (Random Access)​​。因为内存是连续的，通过首地址加上索引偏移量，可以在常数时间O(1)内直接访问到任何一个元素。
• ​​检索​​：在无序数组中查找，只能从头到尾遍历，效率为O(n)。但如果数组是​​有序​​的，就可以利用其随机访问的特性，使用​​二分查找 (Binary Search)​​ 算法，将检索效率大幅提升至O(log n)。

2. 链表 (Linked List)​

• ​​特点​​：不需要连续的内存空间。每个节点（Node）包含数据和指针（Pointer）两部分，指针按顺序将分散的内存空间串起来，形成一条链。正因为存储空间不连续，它​​不具备随机访问的能力​​。
• ​​检索​​：想要访问第i个元素，必须从头部开始，沿着指针链​​逐个遍历​​，直到找到目标，检索效率为O(n)。

3.小结

所有的数据结构都是在数组和链表的基础上进行不同维度上的结合与变化。如：栈和队列本质上是​​限制了读写位置的数组​​；而更为复杂的树、图等结构，其底层也离不开指针（链）和连续内存（数组）的概念。

二、如何提升链表的查询效率？

对于​​非连续存储但有序的链表​​，能否使用二分查找提升其检索效率？二分查找的核心思想是对有序的数组不断折半查询，对于非连续存储的有序链表而言，由于它不具备“随机访问”的特性，是不是可以将它改造为从 “中间节” 访问？

将 M 节点改为带两个指针(双向链表)，指向 L 节点和 R 节点，中间节点作为根节点，其他节点依次类推，便形成了一个​​二叉搜索树（BST）。

在二叉搜索树中，检索时从根节点开始，比较目标值与当前节点值，根据比较结果决定进入左子树或右子树。每次比较都排除掉将近一半的数据，理想情况下检索效率为O(log n)。

三、解决树的平衡问题

1.AVL数

动态的插入和删除操作下，BST极易​​退化​​。如果插入的数据是有序的（如1,2,3,4,5），BST会退化成一条链表，时间复杂度重新变为O(n)，为了解决退化问题，​​平衡二叉搜索树（Balanced BST）​​ 被提出，通过特定的旋转操作来维持树的平衡。

​​AVL 树​​：​​高度平衡树​​：要求任何节点的左右子树高度差（平衡因子）的绝对值不超过1。这种严格的平衡保证了查询性能极致稳定（O(log n)），但为了维持平衡，在插入和删除时需要进行的​​旋转操作更频繁​​，牺牲了部分写操作性能。

• 平衡条件，任意节点的左右子树高度差不超过1
• 在插入或删除后，从失衡节点向上回溯到第一个不平衡的祖先节点，通过旋转最小失衡子树来恢复平衡。
• 旋转后需递归调整祖先节点的高度，确保整棵树满足AVL性质。AVL的旋转更频繁，但能保证最优查询效率（O(log n)）

2.红黑树​​：

​​近似平衡树​​，通过一套复杂的着色和旋转规则，确保从根到叶子的最长路径不会超过最短路径的2倍。这种​​非严格的平衡​​特性，使得红黑树在插入和删除时所需的​​旋转操作比AVL树少​​，从而在读写操作之间取得了更好的综合性能。这是为什么Java的HashMap、C++的STL等众多语言的基础库更倾向于使用红黑树的根本原因。

• 维护五大性质，如根节点黑、红节点无红子节点、黑高一致等
• 通过旋转和变色局部调整结构，减少路径黑高变化的影响。
• 通过旋转将问题节点上移或重新分布颜色，最终通过有限的调整（最多三次旋转）恢复平衡。

AVL树​​适合读多写少的场景，如数据库索引的内存部分。红黑树​​适合读写混合、对综合性能要求高的场景，如系统级的Map、Set实现。

3.衍生新的优化思路：

跳表 (Skip List)：多层二分的链表，不改变节点本身（仍是单链表节点），而是​​额外增加多级索引​​（“快速通道”）。

核心思想​​：底层是所有数据的有序链表，上一层的索引是下一层的“快车道”，跳跃式地指向更远的节点。检索时从顶层开始，逐层下沉，一步步缩小范围。这是一种典型的​​“空间换时间”​​ 策略，其效率同样可以达到O(log n)，实现简单，常被用于Redis的有序集合（Sorted Set）等场景。

四、追求 O(1) 的极致效率：哈希表 (Hash Table)

前面的检索思想都是建立在“有序“的基础上，想要比O(log n)更极致的速度，就需要抛弃“有序”，追求绝对的“快速定位”。

核心思想​​：通过​​哈希函数​​将键（Key）计算映射为一个​​数组下标​​，直接利用数组的随机访问特性在O(1)时间内完成检索。

• 核心挑战​​：哈希冲突（不同的键映射到同一位置）。
• ​​解决方式​​：
  • ​​开放寻址法​​：从冲突位置开始，按某种规则寻找下一个空位。
  • ​​链表法​​（更常见）：在每个数组下标位置挂载一个链表（或树），将冲突的键值对都放在这个链表中。

优缺点​​：哈希表提供极致的O(1)平均检索效率，但其​​散列存储的无序性，也导致范围查询效率非常低下​​。

五、空间与时间的极致优化​：状态检索

哈希表能做到O(1)，但它需要存储完整的键甚至值，空间开销较大。比如：我们只需知道一个元素​​是否存在​​（例如判断用户名是否已注册），使用完整的哈希表可能浪费空间。

​​1.位图 (Bitmap)​​：

• ​​核心思想​​：用 ​​1 个比特 (bit)​​ 来表示一个元素的状态（存在=1，不存在=0）。相比于用一个int（32位）或一个指针，它极大地​​压缩了存储空间​​。

2.布隆过滤器 (Bloom Filter)​​：为了解决位图的​​冲突问题​​和​​大范围数据表示问题​​而诞生

• ​​核心思想​​：一个哈希函数不够，就用多个！​​ 通过引入多个（k个）独立的哈希函数，并将位图数组​​共享给所有元素使用​​，来大幅降低冲突概率。
• ​​应用场景​​：
  • ​​缓存穿透防护​​：在查询底层数据库前，先用布隆过滤器判断key是否存在。如果不存在，直接返回，避免对数据库的无用冲击。
  • ​​爬虫URL去重​​：快速判断一个URL是否已被抓取过。
  • ​​分布式系统​​：如Cassandra等数据库用其快速判断某数据是否不在当前节点，避免昂贵磁盘IO。

3.高效压缩位图(Roaring bitmaps): 解决位图存储稀疏数据时，导致的空间浪费问题

传统 bitmaps 存入一个 整数 8,000,000 （需要至少23位二进制表示，因 (2^{23} = 8,388,608)），首先要分配1,000,000 字节的空间，然后将第8,000,000个bit位设置为1，但实际上仅存放了一个数据，空间浪费比较大。

核心细想：高位分组、低位查找，高 16 位做为记录的索引 KEY，低 16 位作为记录的值 VALUE。高 16 位最多有 2^16 个KEY，每个也叫 HASH Bucket（桶）,每个 Bucket 的大小就是低 16 位存储的记录数。

分桶机制：

• 将32位整数按高16位拆分成 (2^{16} = 65,536) 个桶（Container）。
• 每个桶负责存储低16位的数据（范围 (0) ~ (65,535)）。
• 例如：数字8,000,000（二进制00000000 01111010 00100000 00000000）：
  • 高16位：0x007A（十进制122）→ 属于第122号桶。
  • 低16位：0x2000（十进制8,192）→ 存储在该桶内部。

动态分区，将32位整数按高16位分桶（Container），每个桶独立选择三种存储方式：

• Array Container：稀疏数据时用有序短数组 short[]（≤4096元素）
• Bitmap Container：密集数据时用经典位图 long[1024]（8KB 位图）（＞4096元素）
• Run Container：连续值存储为区间（如 11,12,13,14,15,21,22 存为 11,4,21,1）

动态转换规则

• 初始插入：默认使用Array Container（因为稀疏）。
• 当该桶元素超过4,096时：自动转换为Bitmap Container（保证查询效率）。
• 如果数据高度连续：可能转换为Run Container（进一步压缩空间）。

优势：节省内存，自动选择最优容器，比传统位图节省20x+内存

小结：哈希表 (准确，但空间开销大) → 位图 (空间极致压缩，但无法处理冲突) → 布隆过滤器 (共享位图+多重哈希，以可控的误判率换取空间和时间的巨大优势)​ → 高效压缩位图（解决稀疏数据造成的空间浪费问题）

六、为磁盘而生的检索结构：B+树​

当数据量暴增，无法全部存放于内存，必须依赖磁盘时，我们的设计思路就必须转变。磁盘的机械特性（寻道时间、旋转延迟）决定了其​​随机读写速度远慢于顺序读写​​，而一次磁盘I/O操作的成本极高。因此，核心优化目标从减少计算次数变为​​减少磁盘I/O次数​​。 B+ 树给出了将树形索引的所有节点都存在磁盘上的高效检索方案。

核心思想：B+ 树的一个关键设计，就是让一个节点的大小等于一个块的大小。节点内存储的数据，不是一个元素，而是一个可以装 m 个元素的有序数组。这样一来，我们就可以将磁盘一次读取的数据全部利用起来，使得读取效率最大化。

B+树是B-树的一种变体，是专门为磁盘或其他直接存取辅助设备设计的多路平衡搜索树。

1.“矮胖”结构，减少I/O​​：B+树的一个节点（通常设置为一个磁盘页的大小，如4KB或16KB）可以存储​​大量键（key）和指针​​，而不仅仅是两个。这使得树的层级变得非常少（“矮胖”），通常3-4层就能存储亿级数据。

2.顺序访问优势​​：链表适合顺序访问，但随机访问慢。

非叶子节点​​（索引节点）：只存储键和指向子节点的指针，不存储实际数据，这使得一个节点可以容纳更多索引，树更矮。

叶子节点：所有数据记录​​都存储在​​叶子节点​​中，并且所有叶子节点之间通过指针串联成一个​​有序双向链表​​

七、为海量写入而生的存储结构：LSM 树​

写入瓶颈的突破：B+树虽然查询性能优异，但它本质上是一种“原地更新”结构。写入（特别是随机写入）数据时会导致磁盘 I/O 效率低下（需频繁寻道）。

1.LSM树（Log-Structured Merge-Tree）

解决磁盘随机I/O速度过慢的问题，将数据的随机磁盘I/O读写都转化为内存的读写，然后通过批量写入磁盘和延迟合并操作来提高写入性能。​数据首先写入内存中的有序结构（如跳表），达到阈值后批量顺序刷盘生成不可变的 SSTable 文件，写吞吐量提升可达 10 倍以上

读写分离架构​

• ​​MemTable​​：内存中的动态结构，支持高速写入
• ​​WAL（预写日志）​​：保障崩溃恢复，数据写入前先追加到日志
• ​​SSTable（磁盘层）​​：分层存储, 底层文件更大且有序, 通过后台合并（Compaction）消除冗余数据

2.稀疏索引：解决海量数据查询的基石​

核心思想：有序数据的基础上，为数据块的起始记录创建索引项，而不是为每一行创建索引。搜索时，通过索引快速定位到对应的数据块，然后在该数据块内部顺序查找目标记录。

​​SSTable 的查询挑战​​：每个 SSTable 文件内部有序，但大量文件可能导致查询需扫描多个文件（读放大）。例如，查询一个 Key 可能需依次检查 MemTable、L0 到 LN 的多个 SSTable

解决：

• 为每个 SSTable 建立稀疏索引，仅记录 ​​数据块的起始 Key 和磁盘偏移量​​，而非所有 Key。查询时先通过索引定位数据块范围，再加载特定块而非全文件。
• 对于 ​​“Key 不存在”​​ 的最坏查询场景。每个 SSTable 配备一个位图（布隆过滤器），通过哈希函数快速排除不存在的 Key（假阳性率可控），避免无效扫描

​​3.LSM树的优势与代价​​：

• ​​优势​​：​​写入吞吐量极高​​，非常适合写多读少、批量导入数据的场景。
• ​​代价​​：读操作可能需要检查内存和多个SSTable文件，不如B+树高效（但通常通过​​布隆过滤器​​和​​稀疏索引​​来快速判断某个键不存在于某个文件，加速读过程）。
• ​​应用场景​​：​​LSM树是众多NoSQL数据库（如HBase, Cassandra, LevelDB/RocksDB）的存储引擎基石​

八、为AI时代而生的检索：向量检索 (Vector Search)​

传统的检索（如B+树、哈希）依赖于​​精确匹配​​或​​可排序的键​​。但在AI时代，我们经常需要处理图像、音频、文本等非结构化数据。它们的检索方式发生了根本变化：从“精确查找”变为“​​相似性查找​​”。 

​

核心思想​​：将非结构化数据通过AI模型（嵌入模型）转换为一个高维数值向量（Embedding Vector）。检索不再是比较键是否相等，而是​​计算向量之间的“距离”或“相似度”​​（如余弦相似度、欧氏距离），并找到最相似的K个结果（K-Nearest Neighbors, KNN）。

欧几里得距离(Euclidean distance) ：距离计算，值越小越相似

余弦相似度计算：值越大越相似

以披萨特征向量化为例，真实场景会有很多维度，模拟用户需求：一份比较咸、芝士多但不太辣的披萨，AI 通过意图识别将其转为向量表示[7, 9, 2]

余弦相似度最高：四季披萨（0.987）最匹配用户需求，尽管它的芝士量（5）低于用户期望（9），但因辣度（2）完全匹配且咸度（5）接近，综合评分最高。

距离与相似度的矛盾：欧式距离和余弦相似度可能给出不同排序（距离越小越相似 vs 余弦越大越相似），需根据业务选择指标。

实际应用：用户可能更关注某些特征（如芝士量比咸度重要）。可通过加权调整和性能优化（如索引、降维）。

在AI应用中，文本、图像等数据被转换为向量嵌入后存储在向量数据库中（专门用于存储、索引和检索高维的向量数据），支持基于语义相似性的快速检索。这使得它们在语义搜索、推荐系统、图像检索、异常检测、以及作为检索增强生成（RAG）的关键组件等方面表现出色。向量数据库优化了传统数据库不擅长处理的向量运算和高维索引，是现代AI应用的重要基础设施。

九、总结

从​​数组、链表​​的基础，到​​树形结构​​的优化，再到应对磁盘的​​B+树​​和应对海量写入的​​LSM树​​，检索技术的演进始终围绕着​​空间与时间的权衡​​。而​​稀疏索引​​将这种权衡艺术应用于大数据领域，​​向量检索​​则为我们打开了处理非结构化数据的新大门。

补充：其他数据结构