{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 实验 05：pandas 里的位序列——布尔掩码就是位图索引\n", "\n", "## 为什么做这个实验\n", "\n", "- **要验证的现象**：`iris[\"sepal_width\"] == 3.8` 得到的不是一个 True/False，而是一条**长度等于表行数的 0/1 序列**；紧接着的 `iris[mask]` 就是数据库里\"用位图索引取行\"的那一步。整套动作你在 pandas 里天天写，却未必意识到它和数据库位图索引是同一件事。\n", "- **反直觉之处一**：组合两个条件必须写 `&`，不能写 `and`。写 `and` 会抛 `ValueError: The truth value of a Series is ambiguous`——Python 不知道该把 150 个布尔值按\"全部为真\"还是\"任一为真\"来解释，于是拒绝猜测。\n", "- **反直觉之处二**：pandas 的布尔 Series 是**位序列的语义、字节数组的实现**。数据库的位图索引按 **1 比特/行**存并做游程压缩，而 NumPy 用 **1 字节存 1 个布尔**（一行代码就能验证：`a.dtype, a.itemsize` → `bool 1`）。所以**不能**拿 pandas 的内存占用来论证\"位图索引省空间\"——这一点极容易被讲错。\n", "- **学完能回答**：什么样的列才该建位图索引？多条件 AND / OR 在位图上的代价与条件数有没有关系？为什么命中 96% 的选择性下索引反而不如全表扫描？\n", "\n", "## 运行前准备\n", "\n", "```bash\n", "python -m pip install pandas numpy matplotlib seaborn\n", "```\n", "\n", "验证（四行能跑通即可开始）：\n", "\n", "```python\n", "import pandas as pd, numpy as np, seaborn as sns\n", "print(pd.__version__, np.__version__, sns.__version__)\n", "iris = sns.load_dataset(\"iris\")\n", "print(iris.shape) # 期望输出 (150, 5)\n", "```\n", "\n", "若 `sns.load_dataset(\"iris\")` 因网络失败，改用等价的本地/远端 CSV（行数与列名相同即可，后面所有结论不变）：\n", "\n", "```python\n", "iris = pd.read_csv(\"https://raw.githubusercontent.com/mwaskom/seaborn-data/master/iris.csv\")\n", "```\n" ], "id": "8ae4c0de" }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 步骤 1：加载数据，先看清\"表有多少行\"\n", "\n", "后面每一个数字都要拿\"行数 150\"做分母，所以先把形状确认清楚：\n", "\n", "- `iris` 的类型是 `pandas.DataFrame`；\n", "- `iris.shape` 期望为 `(150, 5)`——150 行、5 列；\n", "- 5 列分别是 `sepal_length`、`sepal_width`、`petal_length`、`petal_width`、`species`。\n", "\n", "**为什么用这么小的数据**：位序列的语义与数据量无关。150 行已经足够把\"命中几行\"\"组合后命中几行\"数清楚，而且可以肉眼核对——这正是教学上要的\"可复算\"。\n" ], "id": "f7838c76" }, { "cell_type": "code", "id": "initial_id", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.244679Z", "start_time": "2025-01-08T13:22:18.238357Z" } }, "source": [ "import seaborn as sns\n", "\n", "iris = sns.load_dataset(\"iris\")\n", "iris.head()" ], "outputs": [ { "data": { "text/plain": [ " sepal_length sepal_width petal_length petal_width species\n", "0 5.1 3.5 1.4 0.2 setosa\n", "1 4.9 3.0 1.4 0.2 setosa\n", "2 4.7 3.2 1.3 0.2 setosa\n", "3 4.6 3.1 1.5 0.2 setosa\n", "4 5.0 3.6 1.4 0.2 setosa" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
sepal_lengthsepal_widthpetal_lengthpetal_widthspecies
05.13.51.40.2setosa
14.93.01.40.2setosa
24.73.21.30.2setosa
34.63.11.50.2setosa
45.03.61.40.2setosa
\n", "
" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 11 }, { "cell_type": "code", "id": "a70250acb4ee1fe4", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.267284Z", "start_time": "2025-01-08T13:22:18.265269Z" } }, "source": [ "type(iris)" ], "outputs": [ { "data": { "text/plain": [ "pandas.core.frame.DataFrame" ] }, "execution_count": 12, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 12 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 步骤 2：造第一条位序列\n", "\n", "```python\n", "bit_sequence_1 = iris[\"sepal_width\"] == 3.8\n", "```\n", "\n", "这一行其实做了三件事：\n", "\n", "1. 取出 `sepal_width` 这一列（150 个浮点数）；\n", "2. **逐元素**与 `3.8` 比较，得到 150 个布尔值；\n", "3. 包成一个 `Series`，索引与原来那 150 行一一对应。\n", "\n", "关键在于 `==` 在这里是**逐元素比较**（NumPy 的广播语义），不是\"判断两个对象是否相等\"。这是初学者最容易卡住的地方。\n", "\n", "**预期看到什么**：\n", "\n", "| 检查 | 期望值 |\n", "|---|---|\n", "| `type(bit_sequence_1)` | `pandas.core.series.Series` |\n", "| `bit_sequence_1.dtype` | `bool` |\n", "| `len(bit_sequence_1)` | 150 |\n", "| `int(bit_sequence_1.sum())` | **6** |\n", "\n", "即 `sepal_width == 3.8` 命中 **6** 行，选择性 $6 / 150 = 4.0\\%$。\n", "\n", "同理，`bit_sequence_2 = iris[\"petal_length\"] == 1.9` 命中 **2** 行，选择性 $2/150 = 1.3\\%$。\n" ], "id": "0e4d3f82" }, { "cell_type": "code", "id": "4c18560c27f1e725", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.291845Z", "start_time": "2025-01-08T13:22:18.290175Z" } }, "source": [ "bit_sequence_1 = iris[\"sepal_width\"] == 3.8" ], "outputs": [], "execution_count": 13 }, { "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.329697Z", "start_time": "2025-01-08T13:22:18.327893Z" } }, "cell_type": "code", "source": "type(bit_sequence_1)", "id": "e938451590ea671d", "outputs": [ { "data": { "text/plain": [ "pandas.core.series.Series" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 14 }, { "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.364523Z", "start_time": "2025-01-08T13:22:18.362006Z" } }, "cell_type": "code", "source": "bit_sequence_1", "id": "5405319db23c10e6", "outputs": [ { "data": { "text/plain": [ "0 False\n", "1 False\n", "2 False\n", "3 False\n", "4 False\n", " ... \n", "145 False\n", "146 False\n", "147 False\n", "148 False\n", "149 False\n", "Name: sepal_width, Length: 150, dtype: bool" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 15 }, { "cell_type": "code", "id": "f18cefbee1bfda7f", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.388432Z", "start_time": "2025-01-08T13:22:18.386979Z" } }, "source": [ "bit_sequence_2 = iris[\"petal_length\"] == 1.9" ], "outputs": [], "execution_count": 16 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 步骤 3：`iris[mask]` 就是一次位图索引查找\n", "\n", "`iris[bit_sequence_1]` 做了一件很朴素的事：**保留布尔值为 `True` 的行，丢掉 `False` 的行**。\n", "\n", "把它翻译成数据库语言：这就是\"取出 `sepal_width = 3.8` 对应的那条位序列，值为 1 的行就是结果\"——一次完整的位图索引查找。\n", "\n", "**预期看到什么**：\n", "\n", "| 表达式 | 期望行数 |\n", "|---|---|\n", "| `iris[bit_sequence_1]` | 6 |\n", "| `iris[bit_sequence_2]` | 2 |\n", "\n", "注意这里**没有发生任何\"逐行 if 判断\"**：pandas 拿到的是一条已经算好的位序列，只是按它去取行。这一区别在数据量上百万行时就是实验 04 里那 101× 差距的来源。\n" ], "id": "72a54bfa" }, { "cell_type": "code", "id": "29cb424385c7f592", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.417909Z", "start_time": "2025-01-08T13:22:18.414211Z" } }, "source": [ "iris[bit_sequence_1]" ], "outputs": [ { "data": { "text/plain": [ " sepal_length sepal_width petal_length petal_width species\n", "18 5.7 3.8 1.7 0.3 setosa\n", "19 5.1 3.8 1.5 0.3 setosa\n", "44 5.1 3.8 1.9 0.4 setosa\n", "46 5.1 3.8 1.6 0.2 setosa\n", "117 7.7 3.8 6.7 2.2 virginica\n", "131 7.9 3.8 6.4 2.0 virginica" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
sepal_lengthsepal_widthpetal_lengthpetal_widthspecies
185.73.81.70.3setosa
195.13.81.50.3setosa
445.13.81.90.4setosa
465.13.81.60.2setosa
1177.73.86.72.2virginica
1317.93.86.42.0virginica
\n", "
" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 17 }, { "cell_type": "code", "id": "445374ff791d771f", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.454388Z", "start_time": "2025-01-08T13:22:18.450925Z" } }, "source": [ "iris[bit_sequence_2]" ], "outputs": [ { "data": { "text/plain": [ " sepal_length sepal_width petal_length petal_width species\n", "24 4.8 3.4 1.9 0.2 setosa\n", "44 5.1 3.8 1.9 0.4 setosa" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
sepal_lengthsepal_widthpetal_lengthpetal_widthspecies
244.83.41.90.2setosa
445.13.81.90.4setosa
\n", "
" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 18 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 步骤 4：把两条位序列按位与——本实验的关键一步\n", "\n", "```python\n", "iris[bit_sequence_1 & bit_sequence_2]\n", "```\n", "\n", "不做任何逐行比较，只把两条位序列**按位与**，就得到了同时满足两个条件的行。这就是位图索引的全部要义。\n", "\n", "**预期看到什么**：命中 **1** 行，即第 44 行 `setosa`（`sepal_length=5.1, sepal_width=3.8, petal_length=1.9, petal_width=0.4`）。\n", "\n", "三个运算符与 SQL 的对应关系：\n", "\n", "| pandas 写法 | 语义 | SQL |\n", "|---|---|---|\n", "| `m1 & m2` | 两个条件都满足 | `WHERE a AND b` |\n", "| `m1 \\| m2` | 至少一个满足 | `WHERE a OR b` |\n", "| `~m1` | 不满足 | `WHERE NOT a` |\n", "\n", "容斥关系可以直接验证：$|A \\cup B| = |A| + |B| - |A \\cap B| = 6 + 2 - 1 = 7$，所以 `m1 | m2` 命中 **7** 行；`~m1` 命中 $150 - 6 = 144$ 行。\n", "\n", "> **必须记住的一条硬性规则**：组合掩码只能用 `&` `|` `~`，**不能**用 `and` `or` `not`。\n", "\n", "```python\n", "iris[bit_sequence_1 and bit_sequence_2]\n", "# ValueError: The truth value of a Series is ambiguous.\n", "# Use a.empty, a.bool(), a.item(), a.any() or a.all().\n", "```\n", "\n", "原因是：`and` 是 Python 的**逻辑连接词**，要求左右两边各自能被解释成一个布尔真值；长度为 150 的 Series 有 150 个布尔值，没有唯一的真假，Python 拒绝猜测。而 `&` 是**按位与运算符**，pandas 为 Series 重载了它，语义是\"逐元素做与\"，正是我们要的。报错信息里列出的 `a.any()` / `a.all()` 是\"把整条 Series 归约成一个布尔值\"的正确写法，适用于\"是否存在满足条件的行\"这类提问。\n", "\n", "另外，多个条件并列时**给每个条件加括号**：`(a > 1) & (b < 2)`。因为 `&` 的优先级高于比较运算符，不加括号会得到莫名其妙的结果。\n" ], "id": "2c319878" }, { "cell_type": "code", "id": "feeaefc1f5e05cfd", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.489267Z", "start_time": "2025-01-08T13:22:18.486186Z" } }, "source": [ "iris[bit_sequence_1 & bit_sequence_2]" ], "outputs": [ { "data": { "text/plain": [ " sepal_length sepal_width petal_length petal_width species\n", "44 5.1 3.8 1.9 0.4 setosa" ], "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
sepal_lengthsepal_widthpetal_lengthpetal_widthspecies
445.13.81.90.4setosa
\n", "
" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "execution_count": 19 }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 步骤 5：pandas 存布尔用的是字节，不是比特\n", "\n", "这是本实验最容易讲错、也最值得亲自动手验的一点。\n", "\n", "```python\n", "import numpy as np\n", "a = bit_sequence_1.to_numpy()\n", "print(a.dtype, a.itemsize) # bool 1 ← 每个布尔占 1 字节（8 比特），不是 1 比特\n", "print(\"150 个布尔占:\", a.nbytes, \"字节\")\n", "print(\"若按 1 比特/行存，只需:\", -(-150 // 8), \"字节\")\n", "```\n", "\n", "期望输出：\n", "\n", "```text\n", "bool 1\n", "150 个布尔占: 150 字节\n", "若按 1 比特/行存，只需: 19 字节\n", "```\n", "\n", "**结论**：pandas 给你的是位序列的**语义与运算方式**，不是它的**压缩存储**。真正的数据库位图索引会把这 150 个比特压进 19 字节，还能再做游程压缩（实验 04 的 WAH：密度 0.1% 时压到 5 个字）。所以**不能**用 pandas 的内存占用来论证\"位图索引省空间\"。\n", "\n", "### 步骤 6：用基数判断\"该不该建位图索引\"\n", "\n", "位图索引按列的**每个取值**各建一条位序列。所以列的基数（不同取值个数）直接决定代价：\n", "\n", "- 要存 $d$ 条长度 $n$ 的位序列，共 $n \\times d$ 个比特；\n", "- 每个取值平均命中 $n/d$ 行。\n", "\n", "$d$ 小（性别、洲、订单状态）时，位序列短、选择性适中，一次位运算能筛掉大量行，很划算；$d$ 大（用户 ID、交易金额、经纬度）时，空间爆炸，且每条位序列几乎全是 0，反而不如直接扫描或换 B+ 树。**经验判据：$d \\ll n$（通常 $d$ 在几十以内）才考虑位图索引。**\n", "\n", "本机实测 iris 各列基数：\n", "\n", "| 列 | 基数 | 是否适合位图索引 |\n", "|---|---:|---|\n", "| `sepal_length` | 35 | 否 |\n", "| `sepal_width` | 23 | 否 |\n", "| `petal_length` | 43 | 否 |\n", "| `petal_width` | 22 | 否 |\n", "| `species` | **3** | **是** |\n", "\n", "**这份数据里只有 `species` 适合位图索引。** 这也解释了为什么前面演示用的是 `== 3.8`、`== 1.9` 这种\"等值但基数不低\"的条件：它们只是为了演示位序列的**运算**，并不代表工程上应该在 `sepal_width` 上建位图索引。\n" ], "id": "c78a5a50" }, { "cell_type": "code", "id": "ebe97cc4effc9455", "metadata": { "ExecuteTime": { "end_time": "2025-01-08T13:22:18.538345Z", "start_time": "2025-01-08T13:22:18.537165Z" } }, "source": [], "outputs": [], "execution_count": null }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 思考题与详解\n", "\n", "> 建议先自己写一遍答案，再展开对照。\n", "\n", "**1. 为什么 `iris[bit_sequence_1 and bit_sequence_2]` 会报错，而 `iris[bit_sequence_1 & bit_sequence_2]` 不会？报错信息里的 \"ambiguous\" 指什么？**\n", "\n", "
答案要点\n", "\n", "`and` 是 Python 的**逻辑连接词**，它要求左右两边各自能被解释成一个布尔真值（`bool(...)`）。长度为 150 的 Series 有 150 个布尔值，Python 不知道该按\"全部为真\"还是\"任一为真\"来解释，因此拒绝猜测，抛：\n", "\n", "```text\n", "ValueError: The truth value of a Series is ambiguous.\n", "Use a.empty, a.bool(), a.item(), a.any() or a.all().\n", "```\n", "\n", "\"ambiguous\"（有歧义）指的就是**这条 Series 没有唯一的真假值**。\n", "\n", "`&` 是**按位与运算符**，pandas 为 Series 重载了它，语义是\"逐元素做与\"，返回一条同样长度的新 Series，正是我们想要的操作。\n", "\n", "顺带一句：报错信息里列出的 `a.any()` / `a.all()` 是\"把整条 Series 归约成一个布尔值\"的正确写法，适用于\"是否存在满足条件的行\"这类提问。\n", "\n", "
\n", "\n", "**2. 位图索引常被说成\"适合低基数列\"。请用本实验的数字说明：给 `sepal_length`（基数 35）建位图索引，代价是什么、收益是什么？**\n", "\n", "
答案要点\n", "\n", "**代价**：要为 35 个不同取值各建一条长度 150 的位序列，共 $150 \\times 35 = 5250$ 个比特（不压缩约 656 字节）。相比只存原始列，索引比数据本身还大——这就是\"空间爆炸\"。\n", "\n", "**收益**：查询 `sepal_length == 5.1` 时，一次位运算就能取出命中的行。但这类等值查询在高基数列上命中极少（本实验 `== 3.8` 只命中 6 行，选择性 4%），用 B+ 树只需 $O(\\log n)$ 次比较就能定位，代价更小。\n", "\n", "**结论**：高基数列上位图索引的维护成本远超收益，应选 B+ 树。位图索引的优势区间是**低基数 + 多条件组合**：多条件 AND/OR 在位图上只是一次位运算，代价与条件数无关；在 B+ 树上却要做多次查找与结果归并，代价随条件数线性增长。\n", "\n", "
\n", "\n", "**3. `~bit_sequence_1` 的选择性是 96%（144/150）。这么高的选择性对查询有什么意义？**\n", "\n", "
答案要点\n", "\n", "选择性 96% 意味着\"几乎每一行都满足\"。此时无论用什么索引，都要返回 144/150 行——索引带来的收益趋近于 0，却仍要付出读取索引结构、做位运算、回表取行的代价。**优化器在选择性很高时应当放弃索引、直接全表扫描**（顺序 I/O 反而更快）。\n", "\n", "业界常见的经验阈值在 5%~30% 之间（随系统而异）：选择性低于阈值走索引，高于阈值走扫描。PostgreSQL 用代价模型而非硬编码阈值来判断，参数 `random_page_cost` / `seq_page_cost` 直接影响这个判断。\n", "\n", "
\n", "\n", "**4. 本实验说\"pandas 的布尔 Series 是位序列的语义、字节数组的实现\"。请设计一个小实验，验证 pandas 在做 `&` 时是否真的用到了 CPU 的位运算并行能力。**\n", "\n", "
答案要点\n", "\n", "思路：把布尔数组用 `numpy.packbits` 压成真正的位（uint8 数组），再对压缩后的数组做 `&`，与直接对原布尔数组做 `&` 比较耗时。若后者没有明显慢于前者，说明 NumPy 内部已经做了批量处理，两者的瓶颈都在内存带宽而非位运算本身；若前者快 8 倍左右，说明 NumPy 是按字节逐元素做的。\n", "\n", "```python\n", "import numpy as np, time\n", "a = np.random.rand(10_000_000) < 0.5\n", "b = np.random.rand(10_000_000) < 0.5\n", "pa, pb = np.packbits(a), np.packbits(b)\n", "\n", "t = time.perf_counter(); [a & b for _ in range(20)]; print(\"字节版\", time.perf_counter() - t)\n", "t = time.perf_counter(); [pa & pb for _ in range(20)]; print(\"压缩版\", time.perf_counter() - t)\n", "```\n", "\n", "注意一个容易搞错的点：`packbits` 本身要花时间。**只做一次** AND 时，压缩再运算通常更慢；只有位序列要被**反复使用**（数据库里的典型情况：索引建一次、查很多次），压缩才划算。这正好解释了为什么数据库愿意在索引上花压缩的代价。**具体耗时需自行实测确认。**\n", "\n", "
\n", "\n", "**5. 数据库里\"位图索引 + B+ 树\"经常被组合使用。请结合实验 03 与实验 04，说明这种组合各自解决什么问题。**\n", "\n", "
答案要点\n", "\n", "- **B+ 树**擅长**范围查询**与**有序遍历**：`WHERE date BETWEEN '2026-01-01' AND '2026-03-31'` 可以沿叶链顺序扫出一段区间，代价与结果集大小成正比，而不是与全表大小成正比。它不擅长多条件组合——每个条件各查一次再归并，代价随条件数线性增长。\n", "- **位图索引**擅长**多条件组合**：`WHERE 条件1 AND 条件2 AND 条件3` 只做两次位与，代价与条件数无关、只与行数有关。它不擅长范围查询——要把范围内每个取值对应的位序列都取出来做 OR，取值多时很快退化。\n", "\n", "所以组合方式是：**用 B+ 树处理范围，用位图处理等值组合**；或先用 B+ 树把候选行圈定到一个较小的集合，再在这个集合上做位运算。这正是很多分析型数据库（以及 PostgreSQL 的 Bitmap Scan 算子）的做法。\n", "\n", "
\n", "\n", "**6. 一张表有 10 亿行、某列基数只有 2（例如\"是否已删除\"），位图索引需要多少个比特？做完游程压缩后大概能压到多少？说出你的估算思路。**\n", "\n", "
答案要点\n", "\n", "不压缩：$10^9$ 个比特 = $10^9/8$ 字节 = 125,000,000 字节 ≈ **119 MiB**。\n", "\n", "压缩后：游程编码（RLE）的压缩率完全取决于\"已删除\"标记在**物理存储顺序上的聚集程度**：\n", "\n", "- 最理想（按删除标记有序存放，只有 2 个游程）：几乎可以压到几十字节。\n", "- 最坏（删除标记随机分布，平均每 2 行切换一次）：游程数约 $5 \\times 10^8$，每个游程按 WAH 的 32 比特字算，反而可能膨胀到 2 GB 以上——**比不压缩还大**。\n", "- 现实通常介于两者之间：若\"已删除\"比例很低（如 1%）且删除行在存储上比较聚集，游程数约等于删除行的\"连续段数\"，压缩率可达数十倍。\n", "\n", "**核心结论**：位图索引的压缩率不是算法的性质，而是**数据分布的性质**。建索引前应该先测，而不是假设。这也正是实验 04 里 WAH 压缩那张图要展示的内容（密度 0.1% 时能压到 5 个字，密度 ≥10% 时压缩失效）。\n", "\n", "
\n", "\n", "**7. 本实验中 `iris[mask]` 只有 150 行，看不出性能差距。要真正观察到\"位图 vs 逐行扫描\"的差距，实验该怎么改？需要注意什么？**\n", "\n", "
答案要点\n", "\n", "改动方向：\n", "\n", "1. **把数据量提上去**：造一张 100 万行的 DataFrame，构造 5 个掩码，比较 `m1 & m2 & m3 & m4 & m5` 与\"逐行 if 判断\"两种写法的耗时。\n", "2. **注意进程内的局限**：pandas 全程在内存里跑，测出来的差距只包含 CPU 与内存带宽，**不含磁盘 I/O**。数据库里位图索引的真正价值（少读页、少回表）在进程内测不出来。\n", "3. **关注次数而不是墙钟**：可以统计\"被访问的元素个数\"（位运算要扫 $n$ 个比特，逐行判断要扫 $n$ 次并做分支），这个指标比毫秒数稳定。\n", "4. **对照实验 04 的 101×**：那里位图查询 1.5184 ms、朴素查询 153.588 ms。你自己造的实验加速比通常**远小于**这个数，因为朴素写法在 NumPy 下也会被向量化。**具体数字需自行实测确认。**\n", "\n", "
\n" ], "id": "c7b13a9c" } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.12.2" } }, "nbformat": 4, "nbformat_minor": 5 }