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