Sunday, November 29, 2015

Zenefits: Database design

http://weibo.com/3948019741/CEiedqkvX?type=comment


zenefits有很多个部门,是层级结构,比如R&D这个部门下有 software department 部门,而 software department 部门下又有 backend 和 frontend 等等。其中每个部门里有主管,有员工。

请设计数据库表结构来表示这个关系。
学员面试解答
楼主设计了两个Table, 一个表示 department, 一个表示 stuff 其中 department table 中存了 这个部门的上级部门的id,以及子部门 id list, 这样比如下面表示的 R&D 部门没有上级部门,但是有下级部门:software department,然后 software department 的上级是 R&D, 子部门是 frontend、backend

Department Table departmentID, department name, manager id, emloyees, parent id, childrent id ---- 1, R&D, manager_id(123), employee_id_list(124,125), null, children_id_list(2, 3, 4 ...) 2, software department, , (), parent_id(1), children_id_list(3, 4, 5)

3, front end 4, back end
Staff Table id, name, department id, ...
然后面试官问如果这个结构要查 RD 所有部门下的员工怎么办。

楼主这个结构只能先把 RD 下面的所有 department id 遍历出来,然后拿着这个 list 去 stuff table 中找了,貌似不太好啊...
不知道大家有什么想法。
解题思路点拨
系统设计班张无忌老师:
需要考虑的要素包括:
Organization table ID, Name, Level, Father,
Staff Table ID Name, OrganizationID

如果简单来做,可以只记录一个staff所在的最底层的OrganizationID。此时看似检索一个大的organization可能需要点时间,但是复杂度其实并不会很高,因为公司人数最多几万人,而且我们如果还建立了索引的话,会更快。
如果想加速的话,可以记录一个staff的OrganizationLevels,例如1.2.3,这样检索的时候就很快了
优化解答参考
感觉自己面试的时候答得不好。谢谢张老师点拨。后来又搜了些资料,发现 mongodb 有篇文章给的比较全面:http://docs.mongodb.org/master/tutorial/model-tree-structures/

总共是五种表示法:
1. 在每个部门中记录子部门的信息
2. 在每个部门中记录父部门的信息
3. 在2的基础上,每个部门中除了 parent,还存储一个 array 结构的 ancestors, 记录所有的祖先
4. 和3类似,但是ancestor不用数组结构,而是使用一个string,记录从顶级部门到当前部门的path
5. 用 nested sets, 给每个部门加上两个字段:left 和 right,分别为中序遍历时的先后到达的序列号。
几个方法各有优劣吧。

1 和 2 比较简单,获取当前 父/子节点非常快,但是要获取一个部门下的所有部门,需要多查询。 3 查询节点下所有子部门只需一个查询即可搞定,比如查Programming下的部门,ancestors 字段中有 Programming 即是,缺点嘛,就是添删了节点后,需要更新该节点的所有子节点,复杂度比较高。另外ancestors字段这里是array类型的,mongodb没问题,不过mysql估计就不支持了。 4 和3类似,只是将ancestors字段打平为一个string结构,这样mysql就能支持了,不过查找时需要正则表达式,感觉效率会略有影响。 5 这个方法挺巧妙的,更具体的可以参考:http://qinxuye.me/article/storing-hierachical-data-in-database/ 优点是查询一个部门的所有子节点会非常快,缺点也是增删会比较复杂。

No comments:

Post a Comment