Title image
红茶馆学习笔记
主页 标签 关于 搜索
开发岗面经合集


如何提高向量数据库检索效率

业界通用的解决方案是近似最近邻搜索（Approximate Nearest Neighbor, ANN）

  1. 核心策略：使用索引技术（换取极少精度的丢失来获得极大的速度提升）

    主流的索引算法包括：

    • HNSW (Hierarchical Navigable Small World - 分层导航小世界):

      原理： 目前最流行、综合性能最好的算法。它像一张分层的地图，顶层是稀疏的高速公路（快速定位大概区域），底层是密集的街道（精确查找）。

      检索速度极快，召回率（Recall）很高。但是 内存占用较高，构建索引较慢。

    • IVF (Inverted File Index - 倒排文件索引):

      原理： 将向量空间划分为多个聚类（Voronoi 单元）。检索时，先找到查询向量属于哪个聚类中心，然后只计算该聚类（及周边几个聚类）内的向量。比如有 100 万个向量，分为 1000 个簇。查询时只需要计算 1/1000 的数据量。

      内存占用可控，速度快。

  2. 进阶策略：向量量化（Quantization）与压缩

    • PQ (Product Quantization - 乘积量化):
      • 将一个高维向量切分成多段，每段分别聚类编码。大幅减少内存占用（通常能压缩几十倍），并且计算距离时使用的是查表法，速度极快。
    • SQ (Scalar Quantization - 标量量化):
      • 将 4 字节的浮点数（Float32）转换为 1 字节的整数（Int8）。内存减少 4 倍，利用 CPU/GPU 的 SIMD 指令集，整数运算比浮点运算快得多。

  3. 架构层面的优化

    • 利用 SIMD 指令集 (AVX-512): 现代 CPU 有专门的向量计算指令，可以并行计算距离。
    • GPU 加速: 使用显卡（如通过 FAISS 库）进行大规模并行计算，对于构建索引和高并发查询有奇效。
    • 分布式与分片 (Sharding): 当单机内存存不下时，将数据切分到多台机器上并行检索，最后汇总结果（MapReduce 模式）。

数据库是怎么建立索引的？

  • 向量数据库

    建立向量索引的过程，本质上是一个对高维空间进行划分和组织的过程。

    1. 基于聚类的索引构建 (以 IVF 为例)

      • 第一步：训练（Training）/ 寻找聚类中心

        数据库会随机抽取一部分向量作为样本。运行 K-Means 算法，将这些样本聚成$N$个簇（比如 1024 个簇）。计算出每个簇的中心点（Centroids）。这些中心点就是第一级路标。

      • 第二步：分配（Assignment）/ 归类

        遍历所有要入库的向量。计算每个向量与这 1024 个中心点的距离。将向量归入距离它最近的那个中心点所代表的桶（Voronoi Cell）中。

      • 结果：

        建立了倒排列表。当你检索时，先算你的查询向量离哪个中心点最近，然后只去那个中心点对应的桶里找。

    2. 基于图的索引构建 (以 HNSW 为例)

      • 核心逻辑：它维护了一个多层的图结构（第 0 层最密，包含所有节点；越往上越稀疏）。新向量插入时，需要找到它在图中的“邻居”，并建立连接（边）。
      • 构建步骤（当插入一个新向量 V 时）：
        1. 随机决定层数： 掷骰子决定这个新向量 V 最高能出现在第几层（比如第 3 层）。这保证了上层节点少（高速公路），下层节点多（社区街道）。
        2. 从顶层开始搜索： 从入口节点开始，在顶层贪婪地向 V 靠近，找到当前层离 V 最近的节点。
        3. 逐层下沉： 带着找到的最近节点进入下一层，继续寻找更近的节点，直到第 0 层。
        4. 建立连接（选邻居）： 在每一层（从 V 能出现的最高层到第 0 层），找到 V 的$M$个最近邻居（Nearest Neighbors），将 V 和这些邻居连上线。
        5. 启发式修剪： 为了防止图太复杂，算法会根据距离和分布策略，切断一些多余的连线，保留最有用的“路”。
      • 结果：
        • 形成了一个“小世界网络”。不管你在图的哪里，通过高速公路（上层）和社区小路（下层），只需跳跃很少的次数就能走到任何一个点。

  • SQL数据库

    传统的 SQL 索引核心几乎都围绕一个概念：**B+ 树 (B+ Tree)**。

    • 扁平且宽（矮胖）： 二叉树太高了，查找次数多。B+ 树的一个节点可以存成百上千个索引项，所以树的高度通常只有 3 到 4 层。这意味着从几十亿条数据中找到一条数据，通常只需要 3 到 4 次磁盘 I/O。
    • 有序排列： 树中的所有数据都是按顺序（如数字大小、字母顺序）排列的。
    • 数据在叶子节点： 非叶子节点（树枝）只存“路标”（Key），所有真正的数据或行指针（Value）都存在最底层的叶子节点上。叶子节点之间有链表相连，方便范围查询（比如 WHERE id > 100）。

    2. 索引的两种主要形式

    在构建索引时，SQL 数据库主要有两种构建方式，理解它们的区别至关重要：

    A. 聚簇索引 (Clustered Index) —— “书的正文”

    • 这不仅仅是索引，它就是数据本身。数据库把整张表的数据行，按照主键（Primary Key）的顺序重新排列存储。
    • 构建过程：
      1. 你指定一个主键（比如 ID）。
      2. 数据库将所有数据行按照 ID 大小进行物理排序。
      3. 建立 B+ 树，叶子节点存储的就是完整的行数据（Row Data）。
    • 特点： 一张表只能有一个聚簇索引（因为数据只能有一种物理排序方式）。

    B. 非聚簇索引 / 二级索引 (Secondary Index) —— “书后的附录”

    • 当你给 user_name 字段建索引时，数据库会新建一棵 B+ 树。
    • 构建过程：
      1. 提取出 user_name 和对应的 主键ID。
      2. 按照 user_name 的字典序排序。
      3. 建立 B+ 树，叶子节点存储的是 user_name + 主键ID（即指针）。
    • 查询流程（回表）： 当你搜 WHERE name = ‘Alice’ 时，数据库先在这个树里找到 Alice，拿到她的 ID（比如 101），然后再去聚簇索引（主键索引）里找 ID=101 的完整数据。这个过程叫**回表 (Look up)**。

MySQL里面有哪些常用的聚合搜索的命令

命令 描述 常用场景 示例 SQL
COUNT() 计数。统计行数。 1. 统计总用户数
2. 统计今日订单量
3. 检查是否存在重复数据		 SELECT COUNT(*) FROM users;
SELECT COUNT(DISTINCT user_id) FROM orders; (去重统计)
SUM() 求和。计算数值列的总和。 1. 计算总销售额 (GMV)
2. 计算库存总量
3. 计算用户累计积分		 SELECT SUM(price) FROM orders WHERE status = ‘paid’;
AVG() 平均值。计算数值列的平均数。 1. 计算客单价 (AOV)
2. 计算学生平均成绩
3. 计算平均响应时间		 SELECT AVG(score) FROM exam_results;
MAX() 最大值。找出列中的最大值。 1. 找出最高分
2. 找出最近一次登录时间 (Max Date)
3. 找出最贵的商品		 SELECT MAX(login_time) FROM user_logs;
MIN() 最小值。找出列中的最小值。 1. 找出最低分
2. 找出最早注册的用户
3. 找出库存最少的商品		 SELECT MIN(price) FROM products;

核心伴随子句 (分组与过滤)

聚合函数通常不会单独使用，而是配合 GROUP BY 和 HAVING 使用，这才是聚合查询的灵魂。

GROUP BY (分组)

  • 作用： 将数据按照一个或多个列进行分类，然后对每一类分别进行聚合。

  • 场景：

    • “每个” 部门有多少人？
    • “每天” 的销售额是多少？
    • “每个类别” 的商品最高价是多少？

  • 示例：

    1
    2
    3
    4
    -- 统计每个部门的平均工资
    SELECT department, AVG(salary) 
    FROM employees 
    GROUP BY department;

HAVING (聚合后过滤)

  • 作用： 对聚合后的结果进行筛选。（注意：WHERE 是对聚合前的原始行进行筛选）。

  • 场景：

    • 找出平均分大于 80 分的班级（先算平均分，再过滤）。
    • 找出累计消费超过 1000 元的 VIP 用户。
    • 找出重复出现超过 3 次的 IP 地址。

  • 示例：

    1
    2
    3
    4
    5
    -- 找出订单总金额超过 1000 的用户
    SELECT user_id, SUM(amount) as total_spent
    FROM orders
    GROUP BY user_id
    HAVING total_spent > 1000; -- 这里不能用 WHERE

如何查找top10热门的商品？

算法：杨氏矩阵找元素

杨氏矩阵的性质是：从左到右递增，从上到下递增。

如果我们选择从右上角开始查找：

  1. 如果当前元素 大于 目标值：因为列是递增的，当前元素已经是该列最小的了，所以目标值不可能在这一列，剔除当前列（向左移动）。
  2. 如果当前元素 小于 目标值：因为行是递增的，当前元素已经是该行最大的了，所以目标值不可能在这一行，剔除当前行（向下移动）。

通过这种方式，每一步都能排除一行或一列，直到找到元素或越界。




▲
▼


:D 获取中...


© - 0nlyb1acktea - 2022 - 2026 - Powered by Hexo Theme Quark