阿C的博客

Date: 2017年4月22日

无限树型表结构的通用设计,最佳字段设计方案如下:

  • 父结点ID:parent_id
  • 结点ID路径:id_path
  • 结点层级:level
  • 是否有子结点:has_children

树型结构的表设计,理解到的,可以有多种设计方式:邻接表枚举路径嵌套集闭包表

设计方式 表数量 查询子 查询树 插入 删除 引用完整性
邻接表 1 简单 简单 简单 简单
枚举路径 1 简单 简单 简单 简单
嵌套集 1 困难 简单 困难 困难
闭包表 2 简单 简单 简单 简单

1、邻接表:最常规、最方便的设计。在递归查询的帮助下,使得邻接表的查询更加高效。
2、枚举路径:少用的设计。能够很直观地展示出祖先到后代之间的路径,但由于不能确保引用完整性,使得这个设计比较脆弱。枚举路径也使得数据的存储变得冗余。
3、嵌套集:很聪明的设计。但不能确保引用完整性,并且只能使用于查询性能要求较高,而其他要求一般的场合使用它。
4、闭包表:最通用的设计。并且最灵活,易扩展,并且一个节点能属于多棵树,能减少冗余的计算时间。但它要求一张额外的表来存储关系,是一个空间换取时间的方案。

参考文章: 逻辑数据库设计 – 单纯的树(递归关系数据) + 查看本文章缓存图

排行榜马太效应,本文介绍如何避免Top产品强者越强而新品上线得不到曝光的情况。

对于 解决排行榜的马太效应 ,工程界提出了很多算法,最著名的包括半衰期算法RedditHacker News的Ranking算法。这里重点介绍一下半衰期算法

放射性元素的原子核有半数发生衰变时所需要的时间,叫半衰期随着放射的不断进行,放射强度将按指数曲线下降,放射性强度达到原值一半所需要的时间叫做同位素的半衰期。

原子核的衰变规律是:N = No * ( 1 / 2 ) ^ ( t / T )其中:No 是指初始时刻( t = 0 )时的原子核数,t 为衰变时间,T 为半衰期,N 是衰变后留下的原子核数。

这里列出我的解释:

  • No:数据的初始值,它是自带单位[1]的。
  • t:数据反应时间,即距离初始值的时间。(曲线变量)
  • T:数据的半衰期,即初始值落到一半的时间。
  • N:数据最终结果,即计算出来的结果值。(结果值)

剔除人为控制,排行榜所涉及的因素无外乎有几个:上架时间、下载量、收藏量、评分、评分人数。将元素的半衰期规律应用到排行榜算法中是一个很好的选择,可以将以上所有因素都结合在这个公式中。

举例:把该公式作用于上架时间,以天作为单位,以一周作为半衰期,会得到这样的一条函数曲线:

简单一点解释(粗俗的来讲):排名榜上产品的名次,随着上架时间的增加,第一天可能计量1:1(指的是1下载量就计1下载量),到第二天就是1:0.9,第十天之后也许就是1:0.1,这样来杜绝强者恒强的情况,做一个平衡。

其他

网上有一个关于分类应用与评分的调整方法。它是这样介绍的:对于参与评分人数,不同的应用可能参与评分的人数不在一个数量级上,这样单纯的引入半衰期公式就会对结果造成过大的影响,因此可以采用将参与评分的人数取对数的方式转换到同一个数量级上,并保持原有的递增规律。调整公式如下:

N = No * ( 1 / 2 ) ^ ( t / T ) * lg(score_num)

参考文章:

脚注

[1] No初始值|单位:如果 No 设置为一天,t 即为几天;如果初始值设置为一小时,t 即为几个小时。

Copyright © 2021 阿C的博客

Theme by AC.AsiaUp ↑