支持“按顺序搜索”的数据结构
-
19-09-2019 - |
题
我想知道我应该使用什么数据结构/存储策略来解决这个问题。
数据库中的每个数据条目由多个有序项的列表组成,例如A-B-C-D,其中A、B、C、D是不同的项。
假设我的数据库中有 3 个条目,
A B C D
E-F-G
G-H-B-A
当用户输入一些无序项目时,我必须从数据库中找到匹配的有序条目。例如,如果用户输入A,B,G,H,我想从数据库返回G-H-B-A给用户。
我的数据存储策略应该是什么?
解决方案
你最好单独存放有序和无序的元素,否则你将需要在有序元素的所有排列,这将是耗时的搜索。
尝试这种情况:
/* Create a table to track your items (A, B, C, etc.). It contains all possible elements */
CREATE TABLE [Items](
[Value] [char](1) NOT NULL,
CONSTRAINT [PK_Items] PRIMARY KEY CLUSTERED ([Value]))
/* Create a table to track their grouping and stated ordering */
CREATE TABLE [Groups](
[ID] [int] NOT NULL,
[Order] [text] NOT NULL,
CONSTRAINT [PK_Groups] PRIMARY KEY CLUSTERED ([ID]))
/* Create a mapping table to associate them */
CREATE TABLE [ItemsToGroups](
[Item] [char](1) NOT NULL,
[Group] [int] NOT NULL
)
ALTER TABLE [ItemsToGroups] WITH CHECK ADD CONSTRAINT [FK_ItemsToGroups_Groups] FOREIGN KEY([Group])
REFERENCES [Groups] ([ID])
ALTER TABLE [ItemsToGroups] CHECK CONSTRAINT [FK_ItemsToGroups_Groups]
ALTER TABLE [ItemsToGroups] WITH CHECK ADD CONSTRAINT [FK_ItemsToGroups_Items] FOREIGN KEY([Item])
REFERENCES [Items] ([Value])
ALTER TABLE [ItemsToGroups] CHECK CONSTRAINT [FK_ItemsToGroups_Items]
/* Populate your tables.
Items should have eight rows: A, B, C,...H
Groups should have three rows: 1:ABCD, 2:EFG, 3:GHBA
Items to groups should have eleven rows: A:1, B:1,...A:3 */
/* You will want to pass in a table of values, so set up a table-valued parameter
First, create a type to support your input list */
CREATE TYPE ItemList AS TABLE (e char(1) NOT NULL PRIMARY KEY)
DECLARE @Input ItemList
GO
/* Create a stored procedure for your query */
CREATE PROCEDURE SelectOrderedGroup @Input ItemList READONLY AS
SELECT *
FROM Groups
WHERE Groups.ID NOT IN (
SELECT [Group]
FROM ItemsToGroups
WHERE Item NOT IN (SELECT e FROM @Input)
)
GO
/* Now when you want to query them: */
DECLARE @MyList ItemList
INSERT @MyList(e) VALUES('G'),('H'),('B'),('A')
EXEC SelectOrderedGroup @MyList
在上面将返回3:GHBA,就像你想要的。如果您在DCBA传给你会回来1:ABCD,再喜欢你正在寻找。如果你在C中传递,你会得到什么,因为没有组只有C的
您可能希望使用表值参数您的输入,如上图所示,但你可以在最后的选择转换成一个简单的列表,丢弃ITEMLIST类型。
其他提示
将列表拆分为单独的项目并在该级别上工作。
一些表:
列表
- 身份证(PK)
- 序列(上面的“A-B-C-D”条目)
- [不管怎么说]
项目
- 身份证(PK)
- 名称(值、单词、任何有意义的内容)
- [不管怎么说]
列表项
- 列表ID
- 商品ID
- [序数 int,如果“G-H-B-A”和“A-B-G-H”被视为不同的序列]
(复合 PK list_ID, item_ID [, ordinal] 在那一项上,基本多:多关系)
一些数据,所以更清楚表格所代表的内容:
INSERT INTO items (ID, name) VALUES (1, 'A'), (2, 'B'), (3, 'G'), (4, 'H');
INSERT INTO lists (ID, sequence) VALUES (1, 'A-B-G-H');
INSERT INTO list_items (list_ID, item_ID) VALUES (1, 1), (1, 2), (1, 3), (1, 4);
INSERT INTO lists (ID, sequence) VALUES (2, 'B-A-G');
INSERT INTO list_items (list_ID, item_ID) VALUES (2, 2), (2, 1), (2, 3);
最后,找到包含的列表 全部 项目(A、B、G、H):
SELECT lists.sequence FROM lists
JOIN list_items ON lists.ID = list_items.list_ID
JOIN items AS i1 ON list_items.item_ID = i1.ID HAVING i1.name = 'A'
JOIN items AS i2 ON list_items.item_ID = i2.ID HAVING i2.name = 'B'
JOIN items AS i3 ON list_items.item_ID = i3.ID HAVING i3.name = 'G'
JOIN items AS i4 ON list_items.item_ID = i4.ID HAVING i4.name = 'H'
这应该返回任何列表,如“A-B-G-H”、“G-H-A-B”、“H-A-T-B-A-G”等,但不返回“B-U-G-H-U-T”(无 A)或“B-A-T-H”(无 G) - 必须满足所有条件。进行“任何”搜索可能会涉及更多一些(在午餐时在我的脑海中写下这个,但是 RIGHT JOIN
单独可能会导致各种重复和缓慢)。
它不会绘制任何基因组图谱或重新定义人类语言,但对于规模相当大的数据集来说应该没问题。无论哪种方式,我都会避免将每个列表存储为 varchar 并执行“WHERE sequence LIKE '%A%' AND sequence LIKE '%B%'
“除非你绝对无法处理添加新数据的额外工作。