数据结构和算法分析架构算法设计模式和编程理论大数据 爬虫Python AI Sql

如何在mysql中实现自然排序

2017-04-16  本文已影响504人  wooyoo

背景

熟悉mysql的同学应该清楚,mysql在对字符串做order by排序时是按照字典序进行排序的,但是如果字符串中包含数字的话(我们称这种类型的字符串为alphanumeric),仅按照字典序的排序结果对用户不太友好。我们举个例子,假设我们在mysql中存了一张files表,里面记录了文件的id以及文件的name,表里的数据如下:

id name
1 1测试2
2 测试
3 1
4 1测试12
5 1测试1
6 1测试20

name字段目前是乱序的,现在我们对该表执行order by查询,即SELECT * FROM files ORDER BY name

id name
3 1
5 1测试1
4 1测试12
1 1测试2
6 1测试20
2 测试

我们重点关注以“1测试”开头的那四个name,他们末尾都带有了数字,但因为mysql默认采取字典序排序,所以排序的结果是"1" < "12" < "2" < "20",这显然不太友好,我们更期望数字部分是根据数字大小排序的。这种非数字部分按照字典序排序,数字部分按照数字大小进行排序的方式我们就称之为自然排序(natural sort)

与字典序排序相比,自然排序的结果更加人性化,对用户更加友好。现代操作系统其实已经实现了文件名的自然排序,我们以Mac为例:

现代的编程语言也都内置了自然排序算法,比如php的natsort方法。但是由于mysql中没有内置对应的函数,我们只能通过其他的办法来实现mysql的自然排序。

思路

要想对mysql做一些扩展,一共有以下三种方法:

  1. 修改底层源码。
  2. 编写mysql扩展(plugin)。
  3. 编写存储函数(stored function)。

显然,要想实现自然排序,我们势必要对order by做一些手脚。如果是第一种方法,不仅难度大,而且不利于mysql的版本升级。如果是第二种方法,mysql扩展又不支持扩展语法层面的能力。那么我们只能采用第三种方法了,也就是存储函数或者又称之为UDF。

如果采用存储函数,那么其实我们在排序时还是用的字典序,所以我们需要借助存储函数将原来待排序的字段(比如例子中的name字段)转换成就算按照字典序排序也能达到自然排序效果的字段。

我们再来看看自然排序的核心思想:非数字部分按照字典序排序,数字部分按照数字大小排序。所以我们只要将数字部分转换成可按大小排序的字符串即可。我们以上例中的”1测试12“和”1测试2“为例,我们将末尾”12“和”2“转化为定长的字段,比如”0000012“和”0000002“。此时”0000012“按照字典序比”0000002“大,这就实现字典序下的自然排序。

好了说了这么多,show me the code:

DELIMITER ;;
CREATE FUNCTION NatSort (Varstring VARCHAR(50))
RETURNS VARCHAR(1000)
READS SQL DATA
DETERMINISTIC
BEGIN
DECLARE v_length INT DEFAULT 0;
DECLARE v_num VARCHAR(50) DEFAULT '';
DECLARE v_index INT DEFAULT 1;
DECLARE v_result VARCHAR(1000) DEFAULT '';
DECLARE v_flag INT DEFAULT 0;
DECLARE v_char CHAR(1) DEFAULT '';
SET v_flag=0;
SET v_index=1;
SET v_length=CHAR_LENGTH(Varstring);

-- 遍历字符串
WHILE v_index <= v_length DO
    SET v_char = mid(Varstring,v_index,1);
    IF (ASCII(v_char)>=48 AND ASCII(v_char)<=57) THEN
        SET v_num=concat(v_num,mid(Varstring,v_index,1)); -- 获取字符串里的数字
        SET v_flag = 1;
    ELSE 
        IF v_flag = 1 THEN
            SET v_flag=0;
            SET v_result=concat(v_result,lpad(cast(v_num AS UNSIGNED),10,'0')); -- 将数字转成定长字符串
            SET v_num=''; -- 重置v_num
        END IF;

        SET v_result=concat(v_result, v_char);
    END IF;
    SET v_index = v_index + 1;
END WHILE;

IF v_flag=1 THEN
    SET v_result=concat(v_result,lpad(cast(v_num AS UNSIGNED),10,'0'));
END IF;

RETURN v_result;
END;;

在上述代码中,我们将所有数字转成了共10位的定长字符串。我们看一下函数的具体效果,我们执行SELECT *, NatSort(name) as name_sort FROM files ORDER BY name_sort

id name name_sort
3 1 0000000001
5 1测试1 0000000001测试0000000001
1 1测试2 0000000001测试0000000002
4 1测试12 0000000001测试0000000012
6 1测试20 0000000001测试0000000020
2 测试 测试

从结果中我们可以看到,已经实现了自然排序,经过实际测试,性能还行。

注意和优化

细心的同学可能已经发现了,上述算法并不完美。我们在代码中将数字扩充为了定长为10位的字符串,那么如果原字符串中的数字长度大于10位,那么算法就失效了。所以在实际使用过程中,要根据具体的业务场景设定定长的位数。

另外,为了提高查询性能,我们可以事先就将转换后的字符串存储在表中,这样就不需要每次查询时都需要调用存储函数。这也是常用的一种以“空间换时间”的优化手段。

本文首发于http://www.kissyu.org/2017/04/16/%E5%A6%82%E4%BD%95%E5%9C%A8mysql%E4%B8%AD%E5%AE%9E%E7%8E%B0%E8%87%AA%E7%84%B6%E6%8E%92%E5%BA%8F/ 转载请标注作者和来源

上一篇下一篇

猜你喜欢

热点阅读