分类 杂记 下的文章

B+树是 B 树的变体,常用于数据库和操作系统的文件系统中,MySQL 数据库的索引就是基于 B+树的实现的,其大致结构如下:

B+ tree

  • B+ Tree 的特点

    • 分为内部节点(非叶子)、叶子结点 2 种节点

      • 内部节点只存储 key,不存储具体数据
      • 叶子节点存储 key 和具体的数据。
    • 所有的叶子节点形成一条有序链表
    • m 阶 B+Tree 树非根节点的元素数量 x :⌈m /2⌉ ≤ x < m

为什么要设计成这样呢?

硬盘的分类

市面上常见的硬盘有:机械硬盘(Hard Disk Drive, HDD),固态硬盘(Solid State Drive,SSD)

硬盘

在这里,我们主要介绍机械硬盘

盘片(platter)、盘面(side)、读写磁头(head)

磁盘剖面图

机器硬盘的剖面图大概就长这个样子。

  • 硬盘一般由多个盘片组成
  • 每个盘片包含包含两个盘面,两面都可以放数据
  • 每个盘面有 1 个对应的读写磁头
  • 盘面、磁头由上到下从 0 开始编号

磁道(track)、扇区(sector)

扇区和磁道

  • 盘面中一圈圈灰色圆环为一条条的磁道
  • 磁道由外到内从 0 开始编码
  • 每个磁道上的一个弧段叫做一个扇区
  • 扇区就是磁盘的最小读写单位
  • 一个扇区的大小通常是 512 字节,也有 4096 字节的

早期磁盘的扇区细节

  • 每条磁道的扇区数是相同,所以外圈扇区的面积会比内圈扇区大
  • 为了更好的读取数据,它们会存放相同的字节数,所以外圈扇区的记录密度要比去内圈小,会浪费大量的空间。
  • 硬盘的存储容量 = 磁头书 盘面磁道数 磁道扇区数 * 扇区字节数

柱面(cylinder)

柱面

想通编号的磁道形成了一个圆柱,成为柱面,磁盘的柱面数与一个盘里面的磁道数是相等得分。

磁盘块

  • 磁盘块,在 Windows 叫做簇(cluster),在 linux 中叫做块(block)
  • 相邻的 2^n 个扇区组合在一起,形成一个磁盘块
  • 操作系统对磁盘进行管理时,以磁盘块作为最小读写单位,一般来说一个磁盘块是 4096 字节(4kb,由 8 个连续的 512 字节扇区组成)

注意:

  • 磁盘块是操作系统中的一个虚拟概念
  • 扇区是磁盘上真实存在的物理区域

操作系统读取硬盘数据的过程

  1. 操作系统将 LBA(Logical Block Address,逻辑块地址) 传送给磁盘驱动器并启动那个读取命令,比如类似设备号 4、磁头号4、磁道号 8、扇区号 6、扇区计数 8 这样的信息。
  2. 磁盘驱动器会根据 LBA 将磁头移动到正确的磁道,盘片开始旋转,将目标扇区旋转到磁盘下
  3. 磁盘控制器将扇区数据等信息传送到一个处于磁盘界面的缓冲区
  4. 磁盘驱动器向操作系统发出“数据就绪”信号
  5. 操作系统从磁盘界面的缓冲区读取数据

    1. 既可以按照一个字节一个字节的方式读取
    2. 也可以启动 DMA(Direct Memory Access,直接内存读取)命令获取

磁盘完成 IO 操作的时间

  • 主要由寻道时间、旋转延迟时间、数据传输时间 3 个部分构成

    • 寻道时间 (seek):将读写磁头移动至正确的磁道上所需的时间,这部分时间代价最高
    • 旋转延迟时间(rotation):磁盘旋转将目标扇区移动到读写磁头下方所需的时间,取决于磁盘转速
    • 数据传输时间(transfer):完成数据传输所需要的时间,取决于接口的数据传输率,通常远小于前两部分消耗时间的
  • 决定时间长短的大部分因素是和硬件相关的,但所需移动的磁道数是可以通过操作系统来进行控制的。

    • 减少所需移动的磁道数是减少整个磁盘读写时间的有效办法
    • 合理安排磁头的移动以减少寻道时间就是磁盘调度算法的目的所在

MySQL 的索引底层为何使用 B+Tree

  • 为了减小 IO 操作数量,一般把一个节点的大小设计成最小读写单位的大小
  • MySQL 的存储引擎 InnoDB 的最小读取单位是 16K
  • 对比 B Tree 和 B+ Tree 的优势:

    • 每个几点存储 key 数量更多,树的高度更低
    • 所有的具体数据都存在叶子节点上,所以每次查询都要查到叶子节点,查询速度比较稳定
    • 所有的叶子节点构成一个有序链表,做区间查询更方便

B-Tree

B 树是一种平衡的多路搜索树,用于文件系统、数据库的实现。

3 阶 B-Tree

4 阶 B-Tree

5 阶 B-Tree

仔细观察 B 树有什么眼前一亮的特点?

  • 一个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点
  • 拥有二叉搜索树的一些性质,我们拿 3 阶 B 树举例,root 节点左侧都是比 18 小的,右侧都是比 48 大的,而中间的节点是在他们两者之间的。
  • 平衡,每个节点所有的子树高度都是一致的。
  • 比较矮

m 阶 B-tree 的性质(m ≥ 2)

  • 假设一个节点存储的元素个数为
  • 根节点: 1 ≤ x ≤ m - 1 :
  • 非根节点:⌈m /2⌉ - 1 ≤ x ≤ m -1
  • 如果有子节点,子节点的个数 y = x + 1

如果我们是 3 阶段 Btree:

  • 根节点:1 ≤ x ≤ 2
  • 非根节点 2≤ y ≤3

因此可以成为(2,3)树、2-3 树。

B 树 VS 二叉搜索树

  • B-Tree 和 二叉搜索树,在逻辑上是等价的

二叉搜索树

3 阶 B-Tree

我们只要让二叉搜索树中的 18 和 33合并成为一个节点,之后再让 23 和 30 合并以此类推,就变成了 B-Tree。所以我们只需要将二叉搜索树的某些父子节点合并后就可以将变成一颗 B-Tree。

  • 多代节点合并可以获得一个超级节点。

    • 2 代合并的超级节点,最多拥有 4 个子节点(至少是 4 阶 B—Tree)
    • 3 代合并的超级节点,最多拥有 8 个子节点(至少是 8 阶 B—Tree)
    • n 代合并的超级节点,最多拥有 2^n 个子节点(至少是 2^n 阶 B—Tree)
  • m 阶 B-Tree,最多需要 log2m 代合并

搜索

B-Tree 的搜索和二叉树的搜索类似。

  1. 先从节点内部从小到大开始搜索元素
  2. 如果命中,搜索结束
  3. 如果未命中,再去对应的子节点中搜索元素,重复步骤 1

添加

新添加的元素必定是添加到叶子节点。

我们现在有一个4 阶B 树。

B-tree

现在我们要向这棵树中插入 55

  1. 首先是与 40 进行比较,发现 55 比 44 大,那么向右子树添加
  2. 右子树中找到了 60~88,55 比 66 小,那么就像左子树添加
  3. 最终我们找到了 50 节点,这个时候新添加的元素必须放在叶子节点上,那么就会将 55 添加 50 上。

B-Tree

现在我们继续向B-Tree 中插入数据 95,按照上面的逻辑执行后。

btree

如果这个时候右下角的子树已经达到了 3 个节点,如果我们再向其中插入 98 呢?如果在加入的话节点就出了 4 阶 B-Tree 的子节点数量。

这个时候就需要进行:上溢(overflow)。

上溢(overflow)

现在假设是 5 阶 B-Tree,一个节点最多存储四个元素。如果存储了五个元素那么就开始上溢。

btree

  • 上溢节点的元素个数必然等于 m
  • 假设上溢节点最中间的元素的位置为 k

    • 将 K 位置的元素向上与父节点合并
    • 将[0, k- 1]和 [k+1, m -1] 位置的元素分裂成两个子节点

      • 这两个子节点的元素个数,必然都不会低于最低限制 ⌈m /2⌉ - 1

btree

这个时候,子节点的上溢会导致父节点的上溢,因为父节点此时也已经超过了最大值,所以一次分裂完毕后,依然按照上述方法进行解决,最极端的情况,可能会一直分裂到根节点。

btree

我们回到上节的那个例子。

b-tree

现在插入 98 后。

98

插入 52:

Untitled

52

插入 54

54

删除

删除 - 叶子结点

如果我们需要删除的元素在叶子结点中,那么直接删除即可。

B-tree

删除- 非叶子节点

  1. 先找到前驱或者后继元素,覆盖所需元素的值
  2. 先把前驱后继元素删除

寻找 60 的前驱和后继:

BTree

Btree

  • 非叶子节点的前驱或后继元素,必须在叶子节点中。
  • 所以这里的删除前驱或后继元素,就是最开始提到的情况:删除的元素在叶子节点中。
  • 真正的删除元素都是发生在叶子节点上。

叶子节点被删除一个元素后,元素个数可能低于最低限制。这种现象称为下溢(underflow)。

下溢

  • 下溢节点的元素数量必然等于 ⌈m /2⌉ - 2

Btree

  • 如果下溢节点临近的兄弟节点,有至少 ⌈m /2⌉ 个元素,可以像其接一个元素

    • 将父节点的元素 b 插入到下溢节点的 0 位置(最小位置)
    • 用兄弟节点的元素 a(最大元素)替代父节点的 yuansub
    • 这种操作其实就是:旋转

B-Tree

B-Tree

B-Tree

图是一颗 5 阶 B-Tre,现在要删除 22,:

  • 如果下溢节点临近的兄弟节点,只有 ⌈m /2⌉ -1 哥元素

    • 将父节点的元素 b 挪下来和左右子节点进行合并
    • 合并后的节点元素个数等于 ⌈m /2⌉ + ⌈m /2⌉ - 2,不会好过 m -1。
    • 这个操作可能会导致父节点下溢,依然按照上述方法解决,下溢现象可能会一直往上传播。

B-Tree

上溢和下溢带来的现象

  • 上溢会让 B-Tree 变高
  • 下溢会让 B-Tree 变矮

什么是算法?

算法理解起来其实非常简单,就是是用于解决特定问题的一系列的执行步骤。

// 计算 a 跟 b 的和
public  static int plus(int a, int b ) {
        return a + b;
}

上面的代码很简单,但是它其实也是一个算法,因为它解决了加法运算。

// 计算 1 + 2 +3 ... +n 的和

public static int sum(int n ) {
        int result =0;
    for (int i = 1; i <= n; i++) {
                result += i
        }
        return result;
}

sum 也是一个算法,它解决了从 1 加到 n 的问题,这两个我们都可以称之为算法,算法其实就是你能解决问题就可以了,小到一行代码,大到上万行都可以称之为算法。

但是当我们使用不同额算法,解决同一个问题,有时效率可能相差非常大。因为我们都知道当我们解决一个问题的时候,解决方案可能会有很多,写代码也是如此,不同算法之间执行效率可能会相差很多。

public static int sum2(int n) {
        return (1 + n) * n / 2;
}

就拿上面从 1 到 n 计算累加的算法,其实让我们如果使用数学公式解决的话,一行代码就搞定了,根本不需要使用循环。

再举个例子:求第 n 个斐波拉切(fibonacci number)

求斐波拉切的方式有很多,在这里我们用两种方案来实现:

  • 递归
public static int fib(int n) {
        if (n <= 1) {
                return n;
        }
        return fib(n - 1) + fib(n - 2);
}

这是一种解决方案,肯定能够解决我们的问题,但是这个算法有性能问题,当我们把 n 写成 64 的时候,这个算法的执行效率就开始降低了,需要执行很久才能够返回。原因我们在后面说,我们先来换一个算法。

  • 动态规划

我们将斐波拉切数列展开:

0 1 1 2 3 5 8 13 ....

我们发现,其实最终值就是前两个值加在一起,那么我们完全可以将前面的值保存起来。


public staitc int fib (int n) {
      if (n <= 1) {
              return n;
      }
   
    int first = 0;
    int second = 1;

    for (int i =0; i < n - 1; i++ ) {
                 int sum = first + second;
        first = second;
            second = sum;
    }
        return second;
}

当我们使用 fib(64) 的时候几乎是秒出结果。

这也就证明了,当我们以后解决问题的时候会有很多种算法,但是算法之间效率相差非常大。这两个算法的差距我们该如何测量呢?

我们可以计算它们给出结果花费时间。

package com.mj;

import java.text.SimpleDateFormat;
import java.util.Date;

public class Times {
    private static final SimpleDateFormat fmt = new SimpleDateFormat("HH:mm:ss.SSS");
    
    public interface Task {
        void execute();
    }
    
    public static void test(String title, Task task) {
        if (task == null) return;
        title = (title == null) ? "" : ("【" + title + "】");
        System.out.println(title);
        System.out.println("开始:" + fmt.format(new Date()));
        long begin = System.currentTimeMillis();
        task.execute();
        long end = System.currentTimeMillis();
        System.out.println("结束:" + fmt.format(new Date()));
        double delta = (end - begin) / 1000.0;
        System.out.println("耗时:" + delta + "秒");
        System.out.println("-------------------------------------");
    }
}

Times 其实就是一个代理,它可以执行满足 Task 的接口的类,然后在执行前后加入时间计数。这样我们就可以统计算法的执行时长了

int = 45
TimeTool.check("fib1", new Task() {
        public void execute() {
        System.out.println(fib1(n));
        }
});

exec

我们对比两个算法之间的差距,可以发现采用动态规划的的方案,随着数字的增大执行时间并不是很大,但是采用递归的方案,时间就慢慢的增加了。

exec

当我们执行 n = 46 的时候,采用递归的方案时间已经达到了 9.44 秒。

如何评判算法的好坏?

还是拿上面的两个案例来举例,我们可以拿代码越短就证明代码越好吗?

肯定不行,在累加中的确是利用公式更好,因为它代码足够简洁,但是在斐波拉切中,反倒是代码更多的执行效率更好。

如果单从执行效率上进行评估,你可能会得到这么一个方案,比较不同算法对同一组输入的执行处理时间这种方案也叫做:事后统计法。

但是这种方案是有以下缺点:

  • 执行时间严重依赖硬件以及运行时各种不确定的因素环境,例如 CPU 更好,当前进程数量比较少等等。
  • 必须编写相应的测试代码
  • 测试数据的选择比较难保证公正性

一般从以下维度来评估算法的优劣

  • 正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
  • 时间复杂性(time complexity):估算程序指令的执行次数(执行时间)
  • 空间复杂度(space complexity):估算所需占用的存储空间

算法的评估

我们来算一下面这个函数需要执行多少条指令

public static void test1(int n) {
        // 汇编指令
        
        // 1
        if (n > 10) { 
            System.out.println("n > 10");
        } else if (n > 5) { // 2
            System.out.println("n > 5");
        } else {
            System.out.println("n <= 5"); 
        }
        
        // 1 + 4 + 4 + 4
        for (int i = 0; i < 4; i++) {
            System.out.println("test");
        }
        
        // 140000
        // O(1) 时间复杂度
        // O(1) 空间复杂度
    }

判断的执行指令次数我们假定是 1,这样算其实不太严谨,但是没有关系,我们先按照这个规则计算。

我们继续向下,到了 for 循环的时候 int i = 0,我们算一个指令,i++ 会执行 4 次,i < 4 会被执行 4 次,for 循环中的打印输出也会执行四次,这样就是 1 + 4 + 4+ 4。总的算下来 就是14。

public static void test2(int n) {
        // O(n)
        // 1 + 3n
        for (int i = 0; i < n; i++) {
            System.out.println("test");
        }
}

int = 0 是 1 次, i < n 执行 n 次, i++ 执行 n 次,输出执行 n 次,那么执行指令的次数就是 1 + 3 * n 次。

public static void test3(int n) {
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 3n^2 + 3n + 1
        // O(n^2)
        
        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }
public static void test5(int n) {
        // 8 = 2^3
        // 16 = 2^4
        
        // 3 = log2(8)
        // 4 = log2(16)
        
        // 执行次数 = log2(n)
        // O(logn)
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
    }

    public static void test6(int n) {
        // log5(n)
        // O(logn)
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
    }

    public static void test7(int n) {
        // 1 + 2*log2(n) + log2(n) * (1 + 3n)
        
        // 1 + 3*log2(n) + 2 * nlog2(n)
        // O(nlogn)
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test10(int n) {
        // O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }

上面的这些函数计算方式都差不多,我就直接列在这里了。

大 O 表示法

我们已经算出了执行指令的大概次数,但是看上去还是很复杂。这个时候我们就要用大 O 表示法来描述复杂度,它表示的是数据规模 N 的一应的复杂度。

规则如下:

  • 忽略常数、系数、低阶

    • 9 >> O(1)
    • 2n + 3 >> O(n)
    • n^2 + 2n + 6 >> o(n^2)
    • 4n^3 + 3n^2 + 22n + 100 >> o(n^3)

上一节中的函数对应的大 O 表示法,在注释中,可以翻回去看一下。大 O 表示法仅仅是一种粗略的分析模型,是一种估算帮助我们短时间内了解一个算法的执行效率。

对数阶的细节

  • 对数阶一般省略底数

常见的复杂度

table

数据规模对比

数据规模较小时候

数据规模较小

数据规模较大时

数据规模较大

这个对比就已经很明显了。

斐波拉切的时间复杂度

斐波拉切的时间复杂度

斐波拉切的时间复杂度

他们的差距有多大?

  • 如果是一台 1GHz 的普通计算机,运算速度 10^9 次每秒(n 为 64)
  • O(n)大约耗时 6.4 * 18^-18 秒
  • O(2^n)大约耗时 584.94 年
  • 有时候算法之间的差距,往往比硬件方面的差距还大

算法的优化方向

  • 用尽量少的存储空间
  • 用尽量少的执行步骤(执行时间)
  • 根据情况:

    • 空间换时间
    • 时间换空间

多个数据规模的情况

public function void test (int n, int k) {
        for (int i = 0; i < n; i++){
                System.out.println("test")
        }

        for (int i = 0; i < k; i++){
                System.out.println("test")
        }
}

这个函数的时间复杂度是由 n 和 k 决定的,O( n + k) 这两个都不能被忽略,因为是两个数据规模

更多的知识

更多的复杂度相关知识,会在后续讲解数据额机构、算法的过程中穿插

  • 更好、更坏复杂度
  • 均摊复杂度
  • 复杂度震荡
  • 平均复杂度

为什么要学数据结构与算法

说到数据结构相信大家的第一反应就是复杂、深奥、难学,至于大家为什么会这么觉得,我认为是没有找对学习资料,只要找对了学习资料相信大家都是可以掌握的。

另外可能会觉着数据结构与算法并不常用,一个产品从开发到上线压根就没有用到数据结构和算法,好像就算我们不懂数据结构与算法也不耽误我们完成研发任务,拿很高的薪资啊,那为什么还要学习数据结构与算法呢?

其实有一个很重要的原因就是我们要应付面试,数据结构和算法可以说是民企面试必考的内容,也就是说国内外一线的大型互联网公司,它在面试的过程中都会多多少少问一些数据结构与算法的问题,而且规模越大的公司,越注重数据结构预算法,甚至现在连一些中小型公司的面试都可能开始问算法题了。

随着时间的推移,面试的难度肯定会越来越高的,这个时候可能会觉着很奇怪,工作中根本用不到算法,那为什么面试的时候还会经常问呢?

这个时候可能会有人觉着委屈,命名研发能力很优秀,但就是因为不会数据结构预算法那大公司就进不了,被大公司拒之门外,但是它整体的综合能力可能会比大公司的一些人要强,这样的情况其实有很多。

在 2015 年 homebrew 的作者去 Google 面试却没有通过面试。

Max Howel

这是他的一条吐槽,内容大概是我们公司百分之九十的人都在用你写的工具,但是你却不能白板编程二叉树的翻转。

但是后来硅谷的大公司都在抢着要他,所以公司面试死盯着算法这一项的确是很容易会误伤很多人才,那为什么要好这么做呢?

其实无论是什么公司都想要招聘优秀的人才,但是你在短短的几个小时面试过程中想要了解一个人的话,其实是真的很困难的,所以很多公司招聘的第一步就是卡学历,因为从概率上讲高学历出现优秀人才的几率肯定会更大一点。

举个例子,一个是计算机硕士但是毫无开发经验,一个是大专学历,有三年开发经验,大公司很有可能会招聘这位硕士,因为大公司会看一个人的长期潜力,如果你不会这个技术,没关系,公司可以进行培训,花时间去培养。

除了通过学历来过滤人才,在面试的时候去考察数据结构和算法也是在短时间内考察一个人长期潜力对的一个捷径。因为数据结构算法功底扎实的程序员,技术实力、业务能力、咨询能力一般都不会差。

还有如果我们问的都是平时工作中常用的技术点,那大家的答案其实都会差不多,而且大家在面试前其实都回去背一下题目,这个时候企业无法去区分人才,算法题就不一样了,这个没法背,考验的是一个人的功底和长期积累,所以通过算法题就可以将人才进行再次区分,进而挑选出更优秀的人才。

所以大公司面试的时候考察这个数据结构和算法不是乱来的,也是有一定的道理的,如果你想要进入更大的公司,数据结构和算法是必须要掌握的。

数据结构与算法的应用

databases

我们平时用的各种数据库在底层肯定用到了数据结构,例如 B 树,hash 表等等这些数据结构,我们平时用数据库的时候直接写 SQL 语句就好了,如果你想重新开发一套数据库,那就必须要会数据结构与算法了。

这些数据库大多数都是由大公司开发出来的,所以大公司对于数据结构与算法的要求肯定会非常高的。

梦幻西游地图

这张截图来自于梦幻西游,我们的游戏人物香葱长安走到阴曹地府,这个时候你就会发现这个游戏会帮助角色规划路线,从长安出发途径建业、东海湾最后到阴曹地府。

规划路线肯定会用到图这种结构,还会用到最短路径算法,游戏开发里面肯定会存在大量的数据结构与算法。

区块链

比特币

区块链和比特币底层也会用到大量的数据结构比如说:链表、二叉树、哈希函数等。

人工智能、VR、AR、自动驾驶

人工智能、VR、AR,无人驾驶肯定是基于数据结构和算法的,可以看出来数据结构和算法可以说是无处不在。

在我们平时的开发中用不到数据结构和算法的原因是因为我们直接使用了很多第三方框架来完成任务,实际上很多第三方框架内部又用到了大量的数据结构与算法,所以如果你懂数据结构和算法的话就可以更好的去阅读这些框架的源码,也更能体会作者的设计思想,更好的使用框架,可以把框架的价值发挥到最大。

你有没有考虑过一个问题,问什么比人能够写出这么优秀的框架?

其实不仅仅是开发第三方框架需要用到算法,你的工作中其实也需要用到数据结构和算法,比如说你的用户量达到上百万,千万,上亿的时候,你要处理海量数据的时候,你怎么可能用不到数据结构算法呢?

如果你一直没用过数据结构和算法有可能你做的一直都是小项目,当你进入更大的平台,更大的用户量的时候,你肯定必然要用到数据结构与算法,所以希望大家再也不要去说数据结构不常用,数据结构没有用的话。

说直接一点,并非是用不上数据结构,而是你的层次还不够。另外计算机编程领域数据结构与算法的应用无处不在的,我们刚才举例的几个场景其实都会应用到大量的数据结构与算法,如果我们的数据结构预算法功底比较扎实的话,我觉着是可以让我们站在更高的角度去思考代码的,写出性能够高的程序。而且也能让我们更快的去上手各种新技术。

学习数据结构预算法也能够让我们打开一扇全新的大门。因为我们这样能够进入更高的编程领域。

为什么有的人学新技术那么快?

比如说人工智能,区块链一出来,很多人已经搞的很厉害了,因为他们的数据结构预算法功底扎实,学的快是很正常的。

接下来的画面可能会很扎心。

都挺好截图

随着年龄的增长,我们的学习能力,体力的确会所有下降,所以趁着脑子还没有生锈,攻克它,一次掌握,终生受益。

Pascal 之父 Nicklaus Wirth 凭借一个公式获得了图灵奖:

算法 + 数据结构 = 程序

可见数据结构与算法在编程领域有多么重要,要不他凭什么一个公式就拿到了图灵奖呢?

基于 MySQL 5.7,这是程序员在囧途的课程笔记,如果需要的话可以关注一下这个网站,有很多 PHP 相关的学习资料,而且很接地气,没有任何复杂概念,博主个人很喜欢。

01 场景案例:实现 select 增加行号

很多时候我们在做一个项目,无论使用的语言是 PHP 还是 Java,不管是为了性能还是业务逻辑,很多时候遇到的瓶颈并不在语言上,而是在数据库上,当然还有一些其他第三方工具,在这里就不进行讲解了,这里的重点是 SQL 思维培养。

首先我们准备一下 SQL。

create table products
(
    p_id   bigint auto_increment comment '产品 id',
    p_name varchar(100)     not null comment '商品名称',
    p_type varchar(50)      not null comment '商品分类,为了演示方便直接使用中文',
    p_view bigint default 0 not null comment '点击量',
    constraint products_pk
        primary key (p_id)
) comment '产品表';

2023-03-22T10:59:48.png

我们现在假设按照点击量进行倒序排列。

select p_name, p_view, p_type
from products
order by p_view desc;

这样就可以按照点击量的顺序取出数据了,接下来我们来显示行号。如果使用过Access 或者 SQl Server 的话它们提供了显示行号的方法,在 MySQL中并没有这样的方法。我们只能够自己实现。

我们首先来引入一个会话变量,我们先来看一下什么是会话变量。

我们可以通过 set 来设置变量:

set @name := 'maksim';
select @name

2023-03-22T11:00:15.png

这样我们就可以在当前绘画中来获取变量了。

这里注意,会话变量只在当前会话有效,当你打开新的会发现获取不到变量的情况。

2023-03-22T11:00:32.png

我们可以利用变量进行累加操作这样就可以实现行号了。

# 设置变量
set @rownum = 0;

# 利用累加实现编号
select p_name, p_view, p_type, @rownum := @rownum + 1
from products
order by p_view desc;

2023-03-22T11:02:18.png

我们不可能每次查询都要重新设置一下@rownum,其实我们可以借助 IFNULL 函数来实现在一条语句中实现获取行号的操作。

  • IFNULL(expr1, expr2) expr1 不为 null,则返回值为 expr1,反之为 expr2
select p_name, p_view, p_type, IFNULL(@rownum := @rownum + 1, @rownum := 1) as rownum
from products
order by p_view desc;

但是现在还有一个问题,当我们再次执行获取数据的语句时候会出现下面的状况。

2023-03-22T11:01:14.png

解决这个问题有两种方案,首先是在每次执行前都重置会话变量,但是这样并没有什么意义。

还有另外一个解决方案,我们可以在关联表后面增加一条语句,对@rownum 进行初始化。

select p_name, p_view, p_type,IFNULL(@rownum := @rownum + 1, @rownum := 1) as rownum
from products,
     (select @rownum := 0) b
order by p_view desc;

这样我们每次执行的结果就都是正确的了。

02 场景案例:分组后在分组内排序、每个分组中取前N条

这个需求在我们做项目的时候经常会碰到,有的时候 SQL 写不出来就会用 ORM 框架反复折腾,这个需求需要配合我们的 SQL 来进行完成。在一些复杂系统中仅仅会一些 ORM 框架是没有用的。

我们依旧使用上节中的数据结构,首先我们取出一个分组后排序的数据。

如果显示 group by 错误,无法显示p_view,可以参考下方链接

一文带你了解mysql sql model的only_full_group_by模式含Error 1055问题分析_ShenLiang2025的博客-CSDN博客

select p_type, p_name, p_view
from products
group by p_type, p_name
order by p_view desc ;

2023-03-22T11:05:10.png

我们可以看到为了满足 p_view的倒排序,列表中类型出现了交叉,分组就没有了意义。为了让类型不交叉,我们只需要在增加 p_type 的排序就可以了。

2023-03-22T11:05:39.png

接下来,我们对其增加序号。

select IF(@back = p_type, @rownum := @rownum + 1, @rownum := 1) as row_num,
       p_type,
       p_name,
       p_view,

       @back := p_type
from (select p_type, p_name, p_view
      from products
      group by p_type, p_name
      order by p_type, p_view desc) a,
     (select @rownum := 0, @bak := '') b;

2023-03-22T11:06:18.png

到这里,你是不是就发现了什么,对,没错,其实这就是我们常见的排行榜。

接下里我们增加单独去两行的操作。

select row_num, p_type, p_name, p_view
from (select IF(@back = p_type, @rownum := @rownum + 1, @rownum := 1) as row_num,
             p_type,
             p_name,
             p_view,

             @back := p_type
      from (select p_type, p_name, p_view
            from products
            group by p_type, p_name
            order by p_type, p_view desc) a,
           (select @rownum := 0, @bak := '') b) c
where c.row_num <= 2

2023-03-22T11:06:56.png

03 场景案例:纯 SQL 也能实现辅助决策统计

如果你只会使用 ORM,那么很多复杂的功能根本做不了,今天我们来实现一个纯 SQL 计算商品的重要度,是否需要进行补货。

很多人认为我们开发 web 只需要增删改查就好了,但是其实如果我们要去做电商平台,或者后台系统,最常见的需求就是统计分析,仅仅是显示商品列表,编辑一下,就很低级。

在 products 表中有点击量这个字段,如果我们工具点击量来依次为依据来判断他为热销商品,那肯定是不对的,因为我们还要去看销售量,在这里我们需要增加一张 products_sales表,来代表销售。

在这里有一个细节,加入我们的商品有那么些,我们的销量就只有几个,所以说并不是所有的商品都有销量。我们不能光靠点击量和销售量当个为依据来进行辅助决策。所以在做后台应用的时候要复杂很多。

2023-03-22T11:08:04.png

2023-03-22T11:08:34.png

我们通过点击量和销售量来做一个评分,然后根据评分辅助决策。

现在我们写一个 SQL,根据分类显示出商品的名称、点击量和销售量情况。没有销售的设置为 0.

select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
from products as a
         left join products_sales b on a.p_id = b.p_id
group by a.p_type, a.p_name
order by a.p_type desc, a.p_view desc;

2023-03-22T11:08:52.png

接下来,我们来计算分类的平均销量。

select p_type, sum(sales) / count(*)
from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
      from products as a
               left join products_sales b on a.p_id = b.p_id
      group by a.p_type, a.p_name
      order by a.p_type desc, a.p_view desc) a
group by p_type

2023-03-22T11:09:03.png

如果需要控制小数点,我们可以增加 round。

select p_type, round(sum(sales) / count(*), 0)
from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
      from products as a
               left join products_sales b on a.p_id = b.p_id
      group by a.p_type, a.p_name
      order by a.p_type desc, a.p_view desc) a
group by p_type

2023-03-22T11:09:16.png

其实这个地方还有问题,那就是我们需要剔除那些没有销量的商品。

select p_type, round(sum(sales) / count(*), 0) as sales_avg
from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
      from products as a
               left join products_sales b on a.p_id = b.p_id
      group by a.p_type, a.p_name
      order by a.p_type desc, a.p_view desc) a
where a.sales > 0
group by p_type

2023-03-22T11:09:27.png

接下来我们计算点击量的平均值。

select p_type, round(sum(p_view) / count(*)) as view_avg
from products
group by p_type

2023-03-22T11:09:55.png

再之后我们将两个 SQL 合并

select a.p_type, p_name, p_view, view_avg, sales, sales_avg
from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
      from products as a
               left join products_sales b on a.p_id = b.p_id
      group by a.p_type, a.p_name
      order by a.p_type desc, a.p_view desc) a,
     (select p_type, round(sum(p_view) / count(*)) as view_avg
      from products
      group by p_type) b,
     (select p_type, round(sum(sales) / count(*), 0) as sales_avg
      from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
            from products as a
                     left join products_sales b on a.p_id = b.p_id
            group by a.p_type, a.p_name
            order by a.p_type desc, a.p_view desc) a
      where a.sales > 0
      group by p_type) c
where a.p_type = b.p_type
  and a.p_type = c.p_type

既然数据我们都有了,就可以进行下一步计算评分了。

2023-03-22T11:10:04.png

我们通过点击量/点击量平均值+销量/销量平均值。

select a.p_type, p_name, p_view / view_avg, sales / sales_avg
from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
      from products as a
               left join products_sales b on a.p_id = b.p_id
      group by a.p_type, a.p_name
      order by a.p_type desc, a.p_view desc) a,
     (select p_type, round(sum(p_view) / count(*)) as view_avg
      from products
      group by p_type) b,
     (select p_type, round(sum(sales) / count(*), 0) as sales_avg
      from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
            from products as a
                     left join products_sales b on a.p_id = b.p_id
            group by a.p_type, a.p_name
            order by a.p_type desc, a.p_view desc) a
      where a.sales > 0
      group by p_type) c
where a.p_type = b.p_type
  and a.p_type = c.p_type

2023-03-22T11:10:25.png

select a.p_type, p_name, (p_view / view_avg + sales / sales_avg)
from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
      from products as a
               left join products_sales b on a.p_id = b.p_id
      group by a.p_type, a.p_name
      order by a.p_type desc, a.p_view desc) a,
     (select p_type, round(sum(p_view) / count(*)) as view_avg
      from products
      group by p_type) b,
     (select p_type, round(sum(sales) / count(*), 0) as sales_avg
      from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
            from products as a
                     left join products_sales b on a.p_id = b.p_id
            group by a.p_type, a.p_name
            order by a.p_type desc, a.p_view desc) a
      where a.sales > 0
      group by p_type) c
where a.p_type = b.p_type
  and a.p_type = c.p_type

这个时候问题出现了,明明是五花肉卖出去的更多,但是猪肉一个没卖出去,平分反倒更高了。所以我们需要对算法增加系数,也就是权重。

2023-03-22T11:10:39.png

select a.p_type, p_name, (p_view / view_avg) * 0.2 + (sales / sales_avg * 0.8)
from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
      from products as a
               left join products_sales b on a.p_id = b.p_id
      group by a.p_type, a.p_name
      order by a.p_type desc, a.p_view desc) a,
     (select p_type, round(sum(p_view) / count(*)) as view_avg
      from products
      group by p_type) b,
     (select p_type, round(sum(sales) / count(*), 0) as sales_avg
      from (select p_type, a.p_name, a.p_view, IFNULL(b.p_sales, 0) as sales
            from products as a
                     left join products_sales b on a.p_id = b.p_id
            group by a.p_type, a.p_name
            order by a.p_type desc, a.p_view desc) a
      where a.sales > 0
      group by p_type) c
where a.p_type = b.p_type
  and a.p_type = c.p_type

2023-03-22T11:11:59.png

这样,运营人员拿到商品就可以分析出哪些商品是需要赶紧补货的。