链表:或如何正确存储实时查询列表

Question

我正在为我们的内部生产开发调度程序。 问题的故事是这样的： 我们有传入的"作业"，这些作业被发送到各个站点的"机器"。 我们将作业列表存储在 MySQL 数据库中。 我想为生产协调员创建一个界面：负责将作业放到正确机器上的人 - 这将包括传入作业的列表，以及代表该机器的作业的每台机器的列表。

我们需要能够执行的一些操作： -重新排序列表而不对 SQL DB 进行大量写入 - 例如将作业放在 que 顶部而不是 que 末尾的机器上，让 que 的其余部分正确更新(级联重新编号是我试图避免的)。

我担心的是可扩展性，如果我们得到10万个工作岗位，或者如果我们大规模增加我们的机器数量。

我们已经考虑过的一些事情 - 并且仍在辩论： 创建具有以下结构的表：作业键、机器 ID、状态、查询位置。具有 queposition 约束在机器 ID 方面是唯一的。 这对于任何数量的机器都有好处，但快速更新 QUE 需要搜索所有数据库以查找每个机器 ID，并且重新排序将不太干净。 另一个想法是有一个预键和后键字段来模拟链表，其中预键是最后一个 QUE 条目的表键，而 Post 将指向下一个条目。 这将解决一些问题，但将麻烦归结为显示 QUE。

这些似乎都不能完全解决问题。

这似乎是一个足够普遍的问题，我相信有一个很好的解决方案 que's - 并在没有冲突的情况下修改所述列表的顺序。 在JavaScript，PHP和MySQL中工作。

Answer 1

拥有"队列位置"列的想法对我来说很有意义。 (继续并结合机器 ID 对该列进行索引。 然后，在查询数据库时，ORDER BY ... DESC此队列位置列和其他一些有意义的列...一个时间戳，比如说。

队列位置值不必是连续的，也不必是唯一的，一个简单的select.. MAX()查询可以告诉您当前存在的最大值(对于特定计算机)。 只需更新要凸到顶部的一行即可。

如果您确实预计会有少量的重新排序，另一个简单的技巧是借用旧的 BASIC 编程时代并使用递增的队列位置值，例如递增10个。 这为您提供了未使用的值，如果您希望您的定位相当准确，您可以使用这些值。 (正如我所说，这些值不必是连续的，也不必是唯一的。

Answer 2

所以你有 100000 个作业，你担心更新作业需要什么工作？ 100000 真的不多。一个标准的mysql数据库应该能够非常快速地处理这些查询。这让我们数据库重新处理所有相关项目。

在 mysql 小提琴上创建架构需要 187 毫秒。

在我的本地开发机器上运行它，插入 100.000 个虚拟行需要 650 毫秒。排序顺序的实际更新？无法衡量。

17：39：40 创建表test(idINT(11) 不空 AUTO_INCREMENT，machine_idINT NULL，job_idINT NULL，sort_orderINT NULL， 主键 (id)， 索引machine(machine_idASC，sort_orderASC)) 受影响的 0 行 0.016 秒

17：39：40 插入test(machine_id、job_id、sort_order)值 (1,1,1) 受影响的 1 行 0.000 秒

17：39：40 插入test(machine_id、job_id、sort_order) 从testT 中选择t.machine_id、t.job_id t.sort_order 受影响的行 记录： 1 重复： 0 警告： 0 0.000 秒

17：39：40 插入test(machine_id、job_id sort_order) 从testt、testt2、testt3testt4 中选择t.machine_id、t.job_id t.sort_order 受影响的 16 行 记录： 16 重复： 0 警告： 0 0.000 秒

17：39：40 插入test(machine_id、job_id、sort_order) 选择t.machine_id、t.job_id、t.sort_ordertesttt、testt2、testt3testt4 受影响的104976行 记录：104976 重复：0 警告：0 0.657 秒

17：39：41 更新测试集 machine_id = 50，其中 ID> 49555，ID <49999 受影响的 443 行 匹配的行数：443 更改：443 警告：0 0.000 秒

17：39：41 更新测试 主内部连接 ( 选择 id， machine_id， @rowNumber ：= @rowNumber + 10 作为 RN 来自测试 ， (选择 @rowNumber ：= 0) VAR 其中 machine_id=50 按 sort_order ASC 排序 ) 作为 t 在 MAIN.id = t.id 组 MAIN.sort_order = t.rn 其中 MAIN.machine_id = 50 受影响的 443 行 匹配行数：443 更改：443 警告：0 0.000 秒

我的建议是：确保你的索引没问题，让数据库做繁重的工作。在代码中进行一些测试，以最大限度地利用数据库，使数据库服务器处于压力之下。让它在 5 分钟内完成一天的工作。我敢打赌，它会站得住脚。

确保您的sort_order在排序之间始终相差 10 个步骤。这样，您始终可以在重新处理相关条目之前插入"9"个作业。 还有一个 ligthweight 关系表，它将作业链接到机器，只有排序顺序作为额外数据，并且可能添加一个主键，以便能够轻松地直接更新作业关系。

以这个演示数据库为例：http://sqlfiddle.com/#!9/3cf11e/1

CREATE TABLE `test` (
`id` INT(11) NOT NULL AUTO_INCREMENT,
`machine_id` INT NULL,
`job_id` INT NULL,
`sort_order` INT NULL,
PRIMARY KEY (`id`),INDEX `machine` (`machine_id` ASC, `sort_order` ASC));

insert into `test` (machine_id, job_id, sort_order) values (1,1,1);
insert into `test` (machine_id, job_id, sort_order) select t.machine_id, t.job_id, t.sort_order from `test` t;
insert into `test` (machine_id, job_id, sort_order) select t.machine_id, t.job_id, t.sort_order from `test` t, `test` t2, `test` t3, `test` t4; 
insert into `test` (machine_id, job_id, sort_order) select t.machine_id, t.job_id, t.sort_order from `test` t, `test` t2, `test` t3, `test` t4; 
update test set machine_id = 50 where id > 49555 and id < 49999;

UPDATE 
test MAIN 
INNER JOIN 
(
SELECT 
id,
machine_id,
@rowNumber := @rowNumber + 10 AS rn
FROM test , (SELECT @rowNumber := 0) var
where machine_id=50
ORDER BY sort_order ASC
) AS t
ON MAIN.id = t.id
SET MAIN.sort_order = t.rn
where MAIN.machine_id = 50;
select * from test where machine_id = 50;

记录计数： 443;执行时间：11ms