代码之家 › 专栏 › 技术社区 › Åukasz W.

分类树搜索的优化解决方案

business-logic-toolkit asp.net-mvc-2 optimization linq c#

Åukasz W. · 技术社区 · 15 年前

背景

我有很多 Category 动态创建并作为此类的表示形式保存在我的数据库中的对象:

class Category
{
    public int Id { get; set; }
    public int ParentId { get; set; }
    public string Name { get; set; }
}

现在每对象可以有多个 InformatonClass 表示该类别中单个信息的对象,例如价格或颜色。这些类也由管理员动态创建并存储在数据库中。对于一组类别有特定的定义。表示它的类如下所示:

class InformationClass
{
    public int Id { get; set; }
    public InformationDataType InformationDataType { get; set; }
    public string Name { get; set; }
    public string Label { get; set; }
}

现在我有了第三个表,表示它们之间的连接,如下所示:

class CategoryInformation
{
    public int InformationClassId { get; set; }
    public int AuctionCategoryId { get; set; }
}

InformationClass 在子类别中。例如,每个产品都有一个价格,所以我需要添加这个

我得知道是哪个 信息类 对象与指定的 类别

所以这是我的问题。对于这个问题,什么是最优化的解决方案?我有一些想法,但我不能决定。

将数据库中的所有类别加载到 Application 表,每次都从这个位置获取它们-只要类别不会经常更改,它将减少数据库请求的数量,但仍然需要使用Linq to对象进行树搜索
还有别的好主意吗?

我将对每一个答案和想法表示感谢。谢谢大家的建议。

2 回复 | 直到 15 年前

Jon Hanna 15 年前

过去(SQLServer2005和LINQ之前)在处理这种结构时(或者更一般的有向无环图的情况,通过连接表实现,以便项可以有多个“父级”),我要么将整个图加载到内存中,或者在数据库中创建一个跳跳虎更新的查找表,该表以祖先到后代的关系缓存。

两者都有优点,哪一个胜出取决于更新频率、父子关系之外对象的复杂性以及更新频率。一般来说,加载到内存允许更快的单个查找,但是对于大型图形,由于每个Web服务器中使用的内存量(这里是“每个”,因为webfarm的情况是将项目缓存在内存中会带来额外问题),它在本机上无法扩展,这意味着您必须非常小心如何处理问题保持同步以抵消这种影响。

现在可用的第三个选项是使用递归CTE执行祖先查找:

CREATE VIEW [dbo].[vwCategoryAncestry]
AS
WITH recurseCategoryParentage (ancestorID, descendantID)
AS
(
    SELECT parentID, id
    FROM Categories
    WHERE parentID IS NOT NULL

    UNION ALL

    SELECT ancestorID, id
    FROM recurseCategoryParentage
        INNER JOIN Categories ON parentID = descendantID
)
SELECT DISTINCT ancestorID, descendantID
FROM recurseCategoryParentage

假设根类别由空parentID表示。

(我们使用UNION ALL,因为我们将在以后选择DISTINCT,这样我们就有了一个DISTINCT操作,而不是重复它)。

这使我们能够在没有非规范化表冗余的情况下执行查找表方法。效率折衷明显不同,通常比使用表的折衷要差,但不多(在选择时略有命中,在插入和删除时略有增加,可忽略的空间增加),但正确性的保证更大。

SELECT DISTINCT (cast(ancestorID as bigint) * 0x100000000 + descendantID) as id, ancestorID, descendantID 并将其定义为 [Column] 属性。当然,所有列都应该表示为DB generated。

CTE代码很简单,上面的视图是您需要的所有额外DB代码,而C#所需的代码是相同的。
虽然在语义上是递归的,但它在某种程度上是查询规划器能够理解和处理的,因此它通常(对于任何深度)只在两个索引扫描(可能是集群的)两个轻量级假脱机、一个串联和一个独特的排序中实现,而不是在您可能想象的许多扫描中实现。因此,虽然扫描肯定比简单的表查找更重,但它远没有人们最初想象的那么糟糕。事实上,即使是这两个索引扫描(同一个表,不同的行)的性质也使得它比您在阅读时想象的要便宜。
如果后来的经验证明这是一种可行的方法,那么用表查找来代替它是非常容易的。
从本质上讲,查寻表将使数据库非规范化。撇开纯度问题不谈,所涉及的“臭味”意味着,这将必须向任何新开发人员解释和证明,因为在那之前,它可能只是“看起来不对”,他们的本能会让他们大惊小怪,试图消除它。

Pro查找表:

虽然CTE的选择速度比人们想象的要快,但是查找速度仍然更快,特别是当用作更复杂查询的一部分时。
虽然cte是sql99标准的一部分,但它们并没有被一些SQL数据库实现,包括SQLServer的旧版本(仍在使用中),这可能会影响任何移植工作。(尽管甲骨文和Postgres等都支持它们,所以在这一点上这并不是一个真正的问题)。

比较(两者)db-heavy选项和内存缓存。

内存中的Pro:

这使得一些二次优化成为可能。
如果以后的评测显示内存中才是正确的选择,那么从DB改为内存中是相当困难的。

Pro查询数据库:

在内存中,启动时间可能非常慢。
对数据的更改要简单得多。大多数观点都是这方面的。实际上,如果您走内存中的路线,那么如何处理使缓存信息无效的更改的问题将成为项目生命周期中一个全新的持续关注的问题,而不是一个微不足道的问题。
如果您使用内存中的存储,那么您可能不得不使用内存中的存储,即使对于与它无关的操作也是如此,这可能会使它与其余数据访问代码的匹配变得复杂。
不需要跟踪更改和缓存新鲜度。
不必确保web场和/或web花园解决方案中的每个web服务器(一定程度的成功将需要这样做)具有完全相同的新鲜度。
类似地,跨机器的可伸缩性程度(通过将web服务器和DB从属服务器的数量增加一倍,可以获得接近100%的额外性能)也更高。
7a.随着项目的发展,这种重内存使用特别喜欢继续增长。
除非更改导致内存存储立即刷新,否则内存中的解决方案将意味着负责管理这些类别的人员使用的视图将与客户看到的视图不同,直到它们重新同步。
除非你在记忆方面很聪明,否则这些尖峰会累积起来,使机器长期处于停滞状态。如果你聪明地避免这种情况,你可能会激怒其他问题。
它是很难从内存中移动到数据库中,这应该证明了这一点。

所有这些都不是100%确定地倾向于一个或另一个解决方案,我当然不会给出一个明确的答案,因为这样做是过早的优化。你能做什么

Timwi 15 年前

Tree structures and DAGs in SQL with efficient querying using transitive closures

其基本思想是:除了 Category CategoryTC 包含 传递闭包 亲子关系。它允许您快速有效地检索特定类别的所有祖先或后代类别的列表。这篇博文解释了如何在每次创建、删除新类别或更改父子关系(每次最多两个查询)时保持传递闭包的最新状态。

你在问题中没有具体说明 InformationClass 表链接到所以我得假设你有 CategoryInformation 如下所示的表:

class CategoryInformation
{
    public int CategoryId { get; set; }
    public int InformationClassId { get; set; }
}

然后您可以使用以下方法获取与特定类别相关联的所有InformationClass:

var categoryId = ...;
var infoClasses = db.CategoryInformation
    .Where(cinf => db.CategoryTC.Where(tc => tc.Descendant == categoryId)
                                .Any(tc => tc.Ancestor == cinf.CategoryId))
    .Select(cinf => db.InformationClass
                      .FirstOrDefault(ic => ic.Id == cinf.InformationClassId));