最近转战学英语语法界,大半时间花在死磕语法书上,疏于打理blog,惭愧。
所幸遇到一本好书: SQL Antipatterns (中文版叫《SQL反模式》)。
我之前对 RDBMS 存在一些非理性的、似是而非的认知,该书以皆反面教材的方式进行了厘清,同时,它对 RDBMS的设计决策亦给出了清晰的路径。
印象比较深刻的有这么两个章节:
一、树
在数据库设计中,树型关系的存储表示一直是一个难题——设计一个有效的树型关系没什么难的,考验人的是如何让这种数据结构在运行时更为直观、高效。
常规的树结构是怎么设计的,大概会有一个表示父结点引用的列,看起来像这样:
1 2 3 4 5 6 |
CREATE TABLE Nodes( node_id INT PRIMARY KEY, node_name VARCHAR(50), parent_id INT, FOREIGN KEY (parent_id) REFERENCES Nodes(node_id) ); |
诚然,这种设计是能run起来的。只是,做为一种反模式 (Adjacency List),它存在如下问题:
- 在查询结点的非直接父级结点时,需要递归查询,性能堪忧
- 父结点对非直接子结点是一无所知,只能回溯
- 结点的挪动,或者枝干删除(可以设置ON DELETE CASCADE约束解决)颇为费劲
书中给出一些设计建议,颇有启发性:
- Path Enumeration,在创建结点时就进行路径的记录,查询方面以空间换时间,每一级结点的层级结构皆表示完备,层级删除或移动需通过代码实现:
node_id | path | node_name |
---|---|---|
1 | 1/ | root |
2 | 1/2/ | child node |
3 | 1/2/3/ | grand child node |
4 | 1/4/ | antoher child node |
- Closure Table,一种更为彻底的全路径结构,分别记录路径上相关结点的全展开形式。能明晰任意两结点关系而无须多余查询,级联删除和结点移动也很方便。但是它的存储开销会大一些,除了表示结点的Meta信息,还需要一张专用的关系表:
ancestor | descendant | ancestor | descendant | ancestor | descendant |
---|---|---|---|---|---|
1 | 1 | 1 | 7 | 4 | 6 |
1 | 2 | 2 | 2 | 4 | 7 |
1 | 3 | 2 | 3 | 5 | 5 |
1 | 4 | 3 | 3 | 6 | 6 |
1 | 5 | 4 | 4 | 6 | 7 |
1 | 6 | 4 | 5 | 7 | 7 |
- 此外,还有Recursive Query、Nested Sets等模式,实效不如上述二者突出,不赘述。
二、图片文件的存储
我的上一份工作是在一家互联网公司服务,刚好他们用户的 avatar 资料就存储在表中(SQL SERVER 的 VarBinary),所以对于这种将二进制数据存储在BLOB字段中的搞法,倒也并不吃惊,只是书中对于为什么不用文件形式存储给出的理由,颇让我信服,也是我之前没有深入思考过的:
- 容灾:DB的备份未必与FileSystem同步,还原亦如是。那么对于用户频繁更新的图片数据,在一次磁盘故障后,你确定还原的volume是最新的版本吗?
- 事务:既然是存储到数据库中的资源引用,就要面临事务考验。事务有成败,用户一个删除动作 fail 掉了,然后文件却被成功干掉了,你怎么向用户解释?
- 一致性:用户上传了新的图片,可你的代码却没有干掉旧的文件,这个 orphan 就一直默默的占据着磁盘空间……
其他章节如 全文检索、Hash加盐、Active Record 也都刷新我的认知,呵呵,以后也能好意思跟人喷,我懂数据库了 ^ ^
打赏作者
您的支持将激励我继续创作!
关于树结构 记录路径用全路径表那就是N*N的矩阵 N为记录个数 我觉得用B树这类的平衡树也是可以的logn的查找更新复杂度还是可以接受的吧
文件 vs BLOB我也十分赞同 最近的项目牵扯越来越多夸平台动态数据交互和函数调用 之前基于文件的形式实在慢而难于保证一致性 不过GPU下数据和CPU下数据互调实在困难 写了一些很丑的内存管理代码 还是得期待NVIDIA对统一内存寻址的更好支持
龙哥多写 我学的很愉快 🙂
话说,你现在在哪家公司做research?
我目前的项目和DARPA合作:http://www.darpa.mil/OpenCatalog/XDATA.html (找Gunrock) 和NVIDIA合作也比较多 用GPU做大数据和图分析吧算是
Team的名字好屌
请见http://blog.csdn.net/Drinkjava2/article/details/54611429,一种简单的树结构存储方案,利用行号和深度两个额外字段即可方便地进行SQL查询/删除/插入。