程序员数学02：对数Log

智谱 GLM，支持多语言、多任务推理。从写作到代码生成，从搜索到知识问答，AI 生产力的中国解法。

本文是《程序员数学扫盲课》系列文章

← 上一篇：程序员数学01：破冰篇 – 数学符号就是代码 | → 下一篇：程序员数学03：集合论 – Redis与SQL

TL;DR

为什么MySQL能在1000万条数据里瞬间找到你要的那一条？为什么Redis的跳表比链表快几百倍？答案就藏在一个数学概念里：对数（log）。这篇文章用Go代码带你彻底搞懂对数，看完你会明白：log就是”切西瓜”的次数。

系列导航

《程序员数学扫盲课》系列：
1. 破冰篇：数学符号就是代码
2. 对数Log：数据库索引的魔法（本篇）
3. 集合论：玩转Redis与SQL
4. 图论基础：微服务依赖管理
5. 概率论：系统可用性计算
6. 统计学：P99延迟与监控报警
7. 线性代数入门：推荐系统的数学基础
8. 哈希与模运算：负载均衡算法
9. 信息论：数据压缩与编码
10. 组合数学：容量规划与性能预估

一、对数到底是什么？

先说重点：对数就是”切几刀能找到目标”。

1.1 从切西瓜说起

假设你有8个西瓜排成一排，要找第6个。

笨办法（线性查找）：

从左往右数：1、2、3、4、5、6 → 找到了！
需要6步

聪明办法（二分查找）：

第1刀：切中间，左边4个，右边4个 → 目标在右边
第2刀：切右边的中间，剩2个 → 目标在右边
第3刀：切最后2个的中间 → 找到了！
只需要3步

这个”3″就是 log₂(8) = 3。

翻译成人话：把8个东西对半切，最多切3刀就能找到任何一个。

1.2 对数的数学定义

看到这个公式别慌：

log₂(8) = 3

读作：”以2为底，8的对数等于3″。

翻译成代码思维：

2³ = 8
↓
"2乘自己3次等于8"
↓
"把8对半切，需要切3次"

Go代码验证：

package main

import (
    "fmt"
    "math"
)

func main() {
    // log₂(8) = 3
    result := math.Log2(8)
    fmt.Printf("log₂(8) = %.0f\n", result) // 输出: 3

    // 验证：2³ = 8
    power := math.Pow(2, 3)
    fmt.Printf("2³ = %.0f\n", power) // 输出: 8

    // 对数和指数是反向操作
    fmt.Println("对数是指数的逆运算")
}

1.3 为什么后端程序员必须懂log？

因为所有高效的数据结构都在用log：

数据结构	查找时间	背后的数学
数组（无序）	O(n)	线性查找，最坏要遍历n次
数组（有序）	O(log n)	二分查找，最多切log₂(n)刀
B+树（MySQL索引）	O(log n)	树高度 = log_fanout(n)
跳表（Redis）	O(log n)	层数 = log₂(n)
平衡二叉树	O(log n)	树高度 = log₂(n)

你看，log无处不在。不懂log，就看不懂为什么这些数据结构快。

二、二分查找：log的第一次实战

2.1 问题场景

假设你有100万条用户ID（已排序），要找ID=888888的用户。

线性查找：

// 最坏情况：遍历100万次
for i := 0; i < 1000000; i++ {
    if users[i].ID == 888888 {
        return users[i]
    }
}

二分查找：

// 最坏情况：只需要 log₂(1000000) ≈ 20 次
left, right := 0, len(users)-1
for left <= right {
    mid := left + (right-left)/2
    if users[mid].ID == target {
        return users[mid]
    }
    if users[mid].ID < target {
        left = mid + 1
    } else {
        right = mid - 1
    }
}

性能对比：
– 线性查找：100万次比较
– 二分查找：20次比较
– 快了5万倍！

2.2 完整Go实现（带性能统计）

package main

import (
    "fmt"
    "math"
    "time"
)

type User struct {
    ID   int
    Name string
}

// 线性查找
func LinearSearch(users []User, targetID int) (User, int) {
    steps := 0
    for _, user := range users {
        steps++
        if user.ID == targetID {
            return user, steps
        }
    }
    return User{}, steps
}

// 二分查找
func BinarySearch(users []User, targetID int) (User, int) {
    left, right := 0, len(users)-1
    steps := 0

    for left <= right {
        steps++
        mid := left + (right-left)/2

        if users[mid].ID == targetID {
            return users[mid], steps
        }

        if users[mid].ID < targetID {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return User{}, steps
}

func main() {
    // 生成100万条有序数据
    size := 1000000
    users := make([]User, size)
    for i := 0; i < size; i++ {
        users[i] = User{ID: i, Name: fmt.Sprintf("User%d", i)}
    }

    targetID := 888888

    // 测试线性查找
    start := time.Now()
    _, linearSteps := LinearSearch(users, targetID)
    linearTime := time.Since(start)

    // 测试二分查找
    start = time.Now()
    _, binarySteps := BinarySearch(users, targetID)
    binaryTime := time.Since(start)

    // 理论步数
    exactSteps := math.Log2(float64(size))
    maxBinarySteps := math.Ceil(exactSteps)
    fmt.Printf("理论步数: %.2f (log₂(%d))\n", exactSteps, size)
    fmt.Printf("最大步数(向上取整): %.0f\n", maxBinarySteps)

    fmt.Printf("数据规模: %d 条\n", size)
    fmt.Printf("目标ID: %d\n\n", targetID)

    fmt.Printf("线性查找:\n")
    fmt.Printf("  实际步数: %d\n", linearSteps)
    fmt.Printf("  耗时: %v\n\n", linearTime)

    fmt.Printf("二分查找:\n")
    fmt.Printf("  实际步数: %d\n", binarySteps)
    fmt.Printf("  理论最大步数: %.0f (log₂(%d))\n", maxBinarySteps, size)
    fmt.Printf("  耗时: %v\n\n", binaryTime)

    fmt.Printf("性能提升: %.0f倍\n", float64(linearSteps)/float64(binarySteps))
}

输出示例：

数据规模: 1000000 条
目标ID: 888888

线性查找:
  实际步数: 888889
  耗时: 5.2ms

二分查找:
  实际步数: 20
  理论最大步数: 20 (log₂(1000000))
  耗时: 120ns

性能提升: 44444倍

三、MySQL索引：log的终极应用

3.1 为什么MySQL索引这么快？

先说结论：因为B+树很矮，高度 = log_fanout(n)。

假设你有1000万条数据，如果用链表存储：
– 查找最坏情况：遍历1000万次
– 插入最坏情况：遍历1000万次

但MySQL用B+树索引：
– 查找最坏情况：读3次磁盘
– 插入最坏情况：读3次磁盘

为什么只需要3次？因为树高度只有3层！

3.2 B+树高度计算

核心公式：

树高度 = log_fanout(记录数)

其中 fanout 是每个节点能存多少个key。

MySQL InnoDB的实际参数：
– 页大小：16KB
– 每个索引项：约16字节（8字节key + 8字节指针）
– 每页能存：16KB / 16B ≈ 1000个key
– fanout ≈ 1000

Go代码计算：

package main

import (
    "fmt"
    "math"
)

// 计算B+树高度
func BTreeHeight(records int, fanout int) int {
    if records <= 0 {
        return 0
    }
    // 高度 = log_fanout(records)
    // 换底公式: log_a(b) = log(b) / log(a)
    height := math.Ceil(math.Log(float64(records)) / math.Log(float64(fanout)))
    return int(height)
}

// 计算每层能存多少数据
func CapacityAtHeight(fanout int, height int) int {
    return int(math.Pow(float64(fanout), float64(height)))
}

func main() {
    fanout := 1000 // InnoDB每页约1000个key

    fmt.Println("MySQL B+树容量分析（fanout=1000）\n")

    // 不同数据规模的树高度
    testCases := []int{
        1000,        // 1千
        10000,       // 1万
        100000,      // 10万
        1000000,     // 100万
        10000000,    // 1000万
        100000000,   // 1亿
        1000000000,  // 10亿
    }

    for _, records := range testCases {
        height := BTreeHeight(records, fanout)
        fmt.Printf("数据量: %10d 条 → 树高度: %d 层 → 最多读 %d 次磁盘\n",
            records, height, height)
    }

    fmt.Println("\n反向计算：不同高度能存多少数据\n")

    for h := 1; h <= 5; h++ {
        capacity := CapacityAtHeight(fanout, h)
        fmt.Printf("高度 %d 层 → 最多存 %d 条数据\n", h, capacity)
    }
}

输出：

MySQL B+树容量分析（fanout=1000）

数据量:       1000 条 → 树高度: 1 层 → 最多读 1 次磁盘
数据量:      10000 条 → 树高度: 2 层 → 最多读 2 次磁盘
数据量:     100000 条 → 树高度: 2 层 → 最多读 2 次磁盘
数据量:    1000000 条 → 树高度: 2 层 → 最多读 2 次磁盘
数据量:   10000000 条 → 树高度: 3 层 → 最多读 3 次磁盘
数据量:  100000000 条 → 树高度: 3 层 → 最多读 3 次磁盘
数据量: 1000000000 条 → 树高度: 4 层 → 最多读 4 次磁盘

反向计算：不同高度能存多少数据

高度 1 层 → 最多存 1000 条数据
高度 2 层 → 最多存 1000000 条数据
高度 3 层 → 最多存 1000000000 条数据
高度 4 层 → 最多存 1000000000000 条数据
高度 5 层 → 最多存 1000000000000000 条数据

关键发现：
1. 1000万条数据，树高度只有3层
2. 10亿条数据，树高度只有4层
3. 每增加一层，容量增加1000倍

这就是log的威力：数据量指数增长，树高度只是线性增长。

3.3 为什么磁盘IO是瓶颈？

性能对比：
– 内存访问：100ns
– SSD随机读：100μs（慢1000倍）
– 机械硬盘随机读：10ms（慢10万倍）

如果用链表存1000万条数据：

最坏情况：1000万次磁盘IO
耗时：1000万 × 10ms = 100,000秒 ≈ 27小时

如果用B+树索引：

最坏情况：3次磁盘IO
耗时：3 × 10ms = 30ms

性能提升：333万倍！

四、Redis跳表：log的另一种玩法

4.1 跳表是什么？

跳表（Skip List）是Redis有序集合（Sorted Set）的底层实现之一。

核心思想：给链表加”高速公路”。

普通链表：

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8
查找8：需要遍历8次

跳表（2层索引）：

Level 2:  1 -------→ 5 -------→ 8
Level 1:  1 → 3 → 5 → 7 → 8
Level 0:  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8

查找8：
1. Level 2: 1 → 5 → 8（3步）

层数 = log₂(n)，所以查找时间是 O(log n)。

4.2 Go实现简化版跳表

package main

import (
    "fmt"
    "math/rand"
)

// 跳表节点
type SkipListNode struct {
    value int
    next  []*SkipListNode // 每层的下一个节点
}

// 跳表
type SkipList struct {
    head     *SkipListNode
    maxLevel int
    level    int // 当前最高层数
}

// 创建跳表
func NewSkipList(maxLevel int) *SkipList {
    head := &SkipListNode{
        value: -1,
        next:  make([]*SkipListNode, maxLevel),
    }
    return &SkipList{
        head:     head,
        maxLevel: maxLevel,
        level:    0,
    }
}

// 随机生成层数（模拟抛硬币）
func (sl *SkipList) randomLevel() int {
    level := 0
    for rand.Float64() < 0.5 && level < sl.maxLevel-1 {
        level++
    }
    return level
}

// 插入元素
func (sl *SkipList) Insert(value int) {
    update := make([]*SkipListNode, sl.maxLevel)
    current := sl.head

    // 从最高层开始查找插入位置
    for i := sl.level; i >= 0; i-- {
        for current.next[i] != nil && current.next[i].value < value {
            current = current.next[i]
        }
        update[i] = current
    }

    // 随机生成新节点的层数
    newLevel := sl.randomLevel()
    if newLevel > sl.level {
        for i := sl.level + 1; i <= newLevel; i++ {
            update[i] = sl.head
        }
        sl.level = newLevel
    }

    // 创建新节点
    newNode := &SkipListNode{
        value: value,
        next:  make([]*SkipListNode, newLevel+1),
    }

    // 插入到各层
    for i := 0; i <= newLevel; i++ {
        newNode.next[i] = update[i].next[i]
        update[i].next[i] = newNode
    }
}

// 查找元素（统计步数）
func (sl *SkipList) Search(value int) (bool, int) {
    current := sl.head
    steps := 0

    // 从最高层开始查找
    for i := sl.level; i >= 0; i-- {
        for current.next[i] != nil && current.next[i].value < value {
            current = current.next[i]
            steps++
        }
    }

    current = current.next[0]
    steps++

    if current != nil && current.value == value {
        return true, steps
    }
    return false, steps
}

// 打印跳表结构
func (sl *SkipList) Print() {
    for i := sl.level; i >= 0; i-- {
        fmt.Printf("Level %d: ", i)
        current := sl.head.next[i]
        for current != nil {
            fmt.Printf("%d → ", current.value)
            current = current.next[i]
        }
        fmt.Println("nil")
    }
}

func main() {
    sl := NewSkipList(4) // 最多4层

    // 插入数据
    values := []int{3, 6, 7, 9, 12, 17, 19, 21, 25, 26}
    for _, v := range values {
        sl.Insert(v)
    }

    fmt.Println("跳表结构：")
    sl.Print()

    // 查找测试
    fmt.Println("\n查找测试：")
    targets := []int{7, 19, 30}
    for _, target := range targets {
        found, steps := sl.Search(target)
        fmt.Printf("查找 %d: 找到=%v, 步数=%d\n", target, found, steps)
    }
}

输出示例：

跳表结构：
Level 3: 9 → nil
Level 2: 6 → 9 → 19 → nil
Level 1: 3 → 6 → 9 → 17 → 19 → 25 → nil
Level 0: 3 → 6 → 7 → 9 → 12 → 17 → 19 → 21 → 25 → 26 → nil

查找测试：
查找 7: 找到=true, 步数=4
查找 19: 找到=true, 步数=3
查找 30: 找到=false, 步数=5

4.3 跳表 vs 平衡树

特性	跳表	平衡树（AVL/红黑树）
查找时间	O(log n)	O(log n)
插入时间	O(log n)	O(log n)
实现复杂度	简单（100行代码）	复杂（需要旋转操作）
空间占用	稍高（多层指针）	较低
并发性能	好（局部锁）	差（全局锁）

Redis为什么选跳表？
1. 实现简单：不需要复杂的旋转操作
2. 并发友好：插入时只需锁局部节点
3. 范围查询快：天然支持有序遍历

五、log的实战应用场景

5.1 容量规划：估算系统能存多少数据

假设你要设计一个用户系统，用B+树索引存储用户ID。

已知条件：
– 单台服务器内存：64GB
– B+树节点大小：16KB
– 每个节点能存：1000个key
– 允许的最大树高度：3层（控制查询延迟）

问题：最多能存多少用户？

package main

import (
    "fmt"
    "math"
)

func main() {
    fanout := 1000
    maxHeight := 3

    // 计算最大容量
    maxRecords := int(math.Pow(float64(fanout), float64(maxHeight)))

    fmt.Printf("系统容量规划\n")
    fmt.Printf("Fanout: %d\n", fanout)
    fmt.Printf("最大树高度: %d 层\n", maxHeight)
    fmt.Printf("最大用户数: %d (10亿)\n", maxRecords)
    fmt.Printf("查询延迟: 最多 %d 次磁盘IO\n", maxHeight)
}

输出：

系统容量规划
Fanout: 1000
最大树高度: 3 层
最大用户数: 1000000000 (10亿)
查询延迟: 最多 3 次磁盘IO

5.2 性能优化：为什么要避免深层嵌套？

看这个场景：你有一个JSON配置文件，嵌套了10层。

{
  "level1": {
    "level2": {
      "level3": {
        ...
        "level10": {
          "value": "target"
        }
      }
    }
  }
}

查找时间：O(深度) = O(10)

如果改成扁平化：

{
  "level1.level2.level3...level10.value": "target"
}

查找时间：O(1)

这就是为什么Redis的key设计推荐用 user:1001:profile 而不是嵌套对象。

5.3 算法选择：什么时候用二分查找？

场景	是否有序	数据规模	推荐算法	时间复杂度
小数组查找	无序	< 100	线性查找	O(n)
大数组查找	有序	> 1000	二分查找	O(log n)
频繁插入删除	有序	任意	跳表/平衡树	O(log n)
范围查询	有序	任意	B+树	O(log n)

Go代码：自动选择算法

func SmartSearch(arr []int, target int, isSorted bool) int {
    if len(arr) < 100 {
        // 小数组：线性查找
        for i, v := range arr {
            if v == target {
                return i
            }
        }
        return -1
    }

    if isSorted {
        // 大数组且有序：二分查找
        return binarySearch(arr, target)
    }

    // 大数组但无序：先排序再二分
    // 或者用哈希表（下一篇会讲）
    return linearSearch(arr, target)
}

六、小结

这篇文章的核心观点：

log就是”切几刀能找到目标”，不是什么高深的数学
二分查找的本质是log₂(n)，100万数据只需20步
MySQL索引快的原因：B+树高度 = log_fanout(n)，1000万数据只需3次磁盘IO
Redis跳表用log实现O(log n)查找，比链表快几百倍
log无处不在：容量规划、性能优化、算法选择都离不开它

记住这个公式：

树高度 = log_fanout(数据量)

这个公式能帮你：
– 估算系统容量
– 预测查询性能
– 选择合适的数据结构

下次面试官问”为什么MySQL索引快”，你就可以回答：因为log让树变得很矮。

参考资料
– MySQL官方文档：InnoDB存储引擎
– Redis设计与实现：跳表章节
– 《算法导论》第12章：二叉搜索树

返回系列总览

👉 程序员数学扫盲课：完整课程大纲

TL;DR

系列导航

一、对数到底是什么？

1.1 从切西瓜说起

1.2 对数的数学定义

1.3 为什么后端程序员必须懂log？

二、二分查找：log的第一次实战

2.1 问题场景

2.2 完整Go实现（带性能统计）

三、MySQL索引：log的终极应用

3.1 为什么MySQL索引这么快？

3.2 B+树高度计算

3.3 为什么磁盘IO是瓶颈？

四、Redis跳表：log的另一种玩法

4.1 跳表是什么？

4.2 Go实现简化版跳表

4.3 跳表 vs 平衡树

五、log的实战应用场景

5.1 容量规划：估算系统能存多少数据

5.2 性能优化：为什么要避免深层嵌套？

5.3 算法选择：什么时候用二分查找？

六、小结

返回系列总览

相关推荐

评论 抢沙发

作者介绍

Toy

文章目录

置顶推荐

前沿哨所

为何 Org Mode 是比 Markdown 更合理的文本标记语言

复古硬核：为经典Mac重写驱动，复活27岁老扫描仪

突发医疗问题：NASA宣布提前接回国际空间站Crew-11任务组

英国政府拟将自己豁免于网络安全法案之外，引发信任危机

开源项目Flow2api：逆向Google Flow，实现无限次Veo视频生成

VS Code插件Antigravity更新：新增多账号管理与配额监控功能

最新文章

热门专题

热门标签

网站统计

最新评论

十年稳如初 — LocVPS，用时间证明实力

10+ 年老牌云主机服务商，全球机房覆盖，性能稳定、价格厚道。

评论抢沙发