在 MySQL 中尽可能走一个 BTREE 索引

Question

假设一个人有一列单词，可以在其上建立BTREE索引：

CREATE TABLE myTable (
  words VARCHAR(25),
  INDEX USING BTREE (words)
);

LOAD DATA LOCAL INFILE '/usr/share/dict/words' INTO TABLE myTable (words);

现在人们想要找到与某些搜索查询共享最长公共前缀的记录，例如'foobar'. 我想这样做：

SELECT DISTINCT words
FROM   myTable
WHERE  words LIKE CASE
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'f%') THEN '%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fo%') THEN 'f%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foo%') THEN 'fo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foob%') THEN 'foo%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'fooba%') THEN 'foob%'
  WHEN NOT EXISTS (SELECT * FROM myTable WHERE words LIKE 'foobar%') THEN 'fooba%'
  ELSE 'foobar%'
END

这很好：它的可读性和性能都很好；它可以很容易地在应用程序代码中生成。

但是，这种搜索应该更容易解决：只需根据搜索词遍历索引树，直到分支不存在，然后返回从当前节点分支的所有结果。

诚然，仅通过一次而不是多次遍历索引可能是不必要的微优化，但感觉好像应该是可能的：是吗？

Answer 1

如果你真的只想遍历b树索引，使用innodb_ruby项目可以帮助 http://blog.jcole.us/2013/01/14/efficiently-traversing-innodb-btrees-with-the-page-directory /

我认为你的查询逻辑是颠倒的。将从最短的单词开始。

我会如何处理它是这样的

DROP PROCEDURE IF EXISTS `find_longest_prefix`;

DELIMITER $$

CREATE PROCEDURE `find_longest_prefix`(IN `word` varchar(255), OUT `word_prefix` varchar(255))
BEGIN
    SET max_sp_recursion_depth = 255;
    SET @nextWord = LEFT(`word`, LENGTH(`word`)-1);

    SELECT COUNT(DISTINCT `words`) FROM `myTABLE` WHERE `words` LIKE CONCAT(`word`, '%') INTO @word_count;

    IF (@word_count > 0)
    THEN
        SET `word_prefix` = `word`;
    ELSE
        IF (LENGTH(@nextWord) > 0)
        THEN
            Call `find_longest_prefix`(@nextWord, `word_prefix`);
        ELSE
            SET `word_prefix` = '';
        END IF;
    END IF;
END$$

DELIMITER ;

这利用了这样一个事实：在 b 树上找到未命中的速度很快，因此我们只需递归地循环调用，直到命中为止。

例子

没有结果

mysql> CALL find_longest_prefix(';autobon', @prefix);
Query OK, 1 row affected (0.01 sec)

mysql> SELECT @prefix;
+---------+
| @prefix |
+---------+
|         |
+---------+
1 row in set (0.00 sec)

一些结果

mysql> CALL find_longest_prefix('autobon', @prefix);
Query OK, 1 row affected (0.00 sec)

mysql> SELECT @prefix;
+---------+
| @prefix |
+---------+
| auto    |
+---------+
1 row in set (0.00 sec)

正如您所看到的，数据是正确的：

mysql> SELECT * FROM myTable WHERE words LIKE 'auto%' OR words LIKE ';auto%';
+----+-----------------+
| id | words           |
+----+-----------------+
| 19 | AUTOCOMMIT      |
| 20 | AUTOEXTEND_SIZE |
+----+-----------------+
2 rows in set (0.00 sec)

此方法应该比实际检查最长步骤之前的每个步骤要快得多，并获得更多返回的数据。

一旦存储过程找到正确的前缀并返回它们（如果您愿意），您应该很容易让存储过程选择行。