Zenefits數(shù)據(jù)庫設(shè)計(jì)面試題
Database Design 題目
zenefits有很多個(gè)部門，是層級結(jié)構(gòu)，比如R&D這個(gè)部門下有 software department 部門，而 software department 部門下又有 backend 和 frontend 等等。其中每個(gè)部門里有主管，有員工。
請?jiān)O(shè)計(jì)數(shù)據(jù)庫表結(jié)構(gòu)來表示這個(gè)關(guān)系。
學(xué)員面試解答
樓主設(shè)計(jì)了兩個(gè)Table， 一個(gè)表示 department， 一個(gè)表示 stuff 其中 department table 中存了 這個(gè)部門的上級部門的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, ...
然后面試官問如果這個(gè)結(jié)構(gòu)要查 RD 所有部門下的員工怎么辦。
樓主這個(gè)結(jié)構(gòu)只能先把 RD 下面的所有 department id 遍歷出來，然后拿著這個(gè) list 去 stuff table 中找了，貌似不太好啊...
不知道大家有什么想法。
解題思路點(diǎn)撥
系統(tǒng)設(shè)計(jì)班張無忌老師：
需要考慮的要素包括：
Organization table ID, Name, Level, Father,
Staff Table ID Name, OrganizationID
如果簡單來做，可以只記錄一個(gè)staff所在的最底層的.OrganizationID。此時(shí)看似檢索一個(gè)大的organization可能需要點(diǎn)時(shí)間，但是復(fù)雜度其實(shí)并不會(huì)很高，因?yàn)楣救藬?shù)最多幾萬人，而且我們?nèi)绻�建立了索引的話，會(huì)更快。
如果想加速的話，可以記錄一個(gè)staff的OrganizationLevels，例如1.2.3，這樣檢索的時(shí)候就很快了
優(yōu)化解答參考
感覺自己面試的時(shí)候答得不好。謝謝張老師點(diǎn)撥。后來又搜了些資料，發(fā)現(xiàn) mongodb 有篇文章給的比較全面：http://docs.mongodb.org/master/tutorial/model-tree-structures/
總共是五種表示法：
1. 在每個(gè)部門中記錄子部門的信息
2. 在每個(gè)部門中記錄父部門的信息
3. 在2的基礎(chǔ)上，每個(gè)部門中除了 parent，還存儲(chǔ)一個(gè) array 結(jié)構(gòu)的 ancestors, 記錄所有的祖先
4. 和3類似，但是ancestor不用數(shù)組結(jié)構(gòu)，而是使用一個(gè)string，記錄從頂級部門到當(dāng)前部門的path
5. 用 nested sets, 給每個(gè)部門加上兩個(gè)字段：left 和 right，分別為中序遍歷時(shí)的先后到達(dá)的序列號(hào)。
幾個(gè)方法各有優(yōu)劣吧。
1 和 2 比較簡單，獲取當(dāng)前 父/子節(jié)點(diǎn)非常快，但是要獲取一個(gè)部門下的所有部門，需要多查詢。 3 查詢節(jié)點(diǎn)下所有子部門只需一個(gè)查詢即可搞定，比如查Programming下的部門，ancestors 字段中有 Programming 即是，缺點(diǎn)嘛，就是添刪了節(jié)點(diǎn)后，需要更新該節(jié)點(diǎn)的所有子節(jié)點(diǎn)，復(fù)雜度比較高。另外ancestors字段這里是array類型的，mongodb沒問題，不過mysql估計(jì)就不支持了。 4 和3類似，只是將ancestors字段打平為一個(gè)string結(jié)構(gòu)，這樣mysql就能支持了，不過查找時(shí)需要正則表達(dá)式，感覺效率會(huì)略有影響。 5 這個(gè)方法挺巧妙的，更具體的可以參考：http://qinxuye.me/article/storing-hierachical-data-in-database/ 優(yōu)點(diǎn)是查詢一個(gè)部門的所有子節(jié)點(diǎn)會(huì)非�？欤秉c(diǎn)也是增刪會(huì)比較復(fù)雜。
更多實(shí)戰(zhàn)面試題
更多討論和面經(jīng)，請移步九章官網(wǎng)“問答”專區(qū)，或點(diǎn)擊“閱讀原文”。
簡介
九章算法,幫助更多中國人找到好工作!
九章算法，團(tuán)隊(duì)成員均為硅谷和國內(nèi)頂尖IT企業(yè)工程師。提供算法培訓(xùn)、面試咨詢、求職內(nèi)推。
目前培訓(xùn)的程序員遍布中國、美國、加拿大、澳大利亞、英國、新加坡等12個(gè)國家和地區(qū)。
目前開設(shè)課程有九章算法班、系統(tǒng)設(shè)計(jì)班、BAT國內(nèi)班、九章算法強(qiáng)化班。更有Java / ios / C++等即將開課。
更多詳情，登錄www.jiuzhang.com，或致信info@ninechapter.com.
【Zenefits數(shù)據(jù)庫設(shè)計(jì)面試題】相關(guān)文章：
數(shù)據(jù)庫面試題及答案05-31
數(shù)據(jù)庫常見面試題01-27
Oracle數(shù)據(jù)庫DBA經(jīng)典面試題02-11
java設(shè)計(jì)模式面試題06-01
數(shù)據(jù)庫設(shè)計(jì)論文致謝詞04-11
HR如何設(shè)計(jì)面試題目02-23