前端開發應更多地使用多層嵌套對象的結構，還是拍平數組進行引用的結構？

以一個三級聯動的需求為例：

多層嵌套對象的方式的數據結構：

[{
label: String,
id: String,
children: [
{
label: String,
id: String,
children: [
{
label: String,
id: String
}
]
}
]
}]


拍平數組進行引用的方式的數據結構：

[
{
label: String,
id: String,
parentId: String
}
]


很多情況下，當然兩種都有比較好。

但這其中最大的關鍵是，需要建立兩者的自動同步機制，如果你做了一會，把兩邊搞得不一致了，那當然不行，但問題是：怎麼儘可能方便地建立這種自動同步的關係？

早些年，在函數式的理念沒有這麼流行之前，我們可以通過引用來建立比較巧妙的數據共享關係，比如說，有一組數據，我們要把它搞成樹的形狀來展示：

const regions = [
{ id: 1, name: "Jiangsu" },
{ id: 2, name: "Zhejiang" },
{ id: 3, name: "Yunnan" },
{ id: 11, name: "Nanjing", parent: 1 },
{ id: 12, name: "Suzhou", parent: 1 },
{ id: 21, name: "Hangzhou", parent: 2 },
{ id: 22, name: "Ningbo", parent: 2 },
{ id: 31, name: "Kunming", parent: 3 },
{ id: 32, name: "Lijiang", parent: 3 },
{ id: 111, name: "Jiangning", parent: 11 },
{ id: 112, name: "Gaochun", parent: 11 },
{ id: 321, name: "Ninglang", parent: 32 },
{ id: 322, name: "Huaping", parent: 32 }
]

return { map, tree }
}


注意這裡返回的結果，是一個map，一個tree（最上一級的元素形成的數組），為什麼要這樣呢？

如果從展現來說，肯定是樹狀結構比較好，因為可以用類似遞歸的方式展示，很自然。但是，如果你要做修改，跨層移動，比如說，把一個樹枝整體移動去另外一個地方，那就不太好辦。

這時候，我們就能發現這個map的好處了，你想修改誰，直接用它的id去map里查，然後修改。所以我們實際上是對同一份數據，做了雙重索引。這個例子裡面的每個region其實只有一份，你修改了map或者tree裡面的，另外一邊也會改，因為就完全是相同引用。

用這種機制，需要注意的是保持好引用的同步關係，比如有新增、刪除操作的時候，要手動兩邊同步。

現在，在一些技術棧裡面，需要immutable的數據，這個辦法就不能接受了（雖然immutable.js的底層還是類似的方式……），那怎麼辦呢，reduce來，reduce去倒是小事，但你要在state裡面存兩份呀，map的那份你又不是用來直接展示的，存裡面會傷害到處女座怎麼辦？要存放在組件里也不對，萬一多個組件都要用到呢？難道放在一個專門get，set的service里！堂堂大service，就充當一個存取器，這樣好嗎？

我們回憶一下，React黨最喜歡吐槽別的框架的是什麼問題，是數據的聯動關係。然而世界上的聯動關係並不是全部基於臟檢測或者setter，也可以通過數據管道的方式啊。

const arr$ = Observable.of(regions)
const tree$ = arr$.map(getTree)


甚至你還可以定義出不同的管道，以arr、map、tree三者中的一個作為源頭，描述出它到其他兩個之間的轉換關係，然後，在修改的時候，往往源頭裡面放修改過的結果即可（這個修改可以是immutable的，React黨用；也可以是非immutable的，Vue黨用；大ng黨好像兩種都可以……），另外兩個的值會自動重算，並且推送給訂閱者。

先說兩種結構的特點。

嵌套結構由於存儲了 children，所以進行 children 相關的操作會非常便利。比如給父節點 id 查、刪 children。但是找某一節點的父節點，或者要 merge 另一棵樹時，就比較麻煩。

而拍平結構（父指針表示法），由於存儲了 parent ，所以進行 parent 相關的操作會比較簡便，而通過 parent 找 children 則比較麻煩。

較好的辦法是優先用嵌套結構，在每個 node 上額外存儲 parent 欄位，另外再加一個 map 保存 id 到 node 的映射。拿空間換時間。嗯。也就是徐叔的方案。剩下的事情徐叔的答案很專業，不贅述。

在實施上，可能還要具體問題具體分析。

如果數據源（介面）本就是分層給的，比如非同步的查省 - 市 - 縣三級聯動，介面默認先給出省，選擇省後再通過省查市，使用嵌套結構是符合直覺的選擇。

又比如數據源本身是以父指針表示法給出的一個數組，但這個數組不是按照前序遍歷產生的話（這個時候最讓後端改），在前端還是要自己遍歷一遍找跟節點並形成一個嵌套的結構的（因為如果直接拿這個非DLR的數組去渲染，會在渲染某些節點的時候發現它的父節點還沒有被渲染出來），在這個過程中自然而然也就有了一個嵌套結構的副本。

數據結構這玩意是為演算法服務的，送進演算法之前數據結構什麼都不是，所以關鍵是你要在前端使用什麼演算法，這個演算法適合使用怎樣的數據結構，就用表示樹為例，有鏈式樹（你的第一種）、父指針表（你的第二種）、邊表、鄰接表、鄰接矩陣等等，每種結構都為不同的演算法服務，而且可以相互轉換，脫離演算法考慮數據結構是毫無意義的，這跟前後端無關。早就說了多學點數據結構和演算法，你們還說沒用，你看看，遇到問題都不知道該怎麼描述……

舉一些這些結構的不同應用場景，最傳統的鏈式樹，也就是你的第一種結構，是用來從根向子節點遍歷用的，許多很重要的演算法比如DFS、BFS通常都會使用這種結構，你一定也自己寫過這些演算法，比如說要把節點渲染成樹狀的HTML標籤，實際上通常就會使用DFS（前端的人一般不會寫BFS……），也就是使用遞歸的方式把標籤一個一個創建出來，只是你們沒發現那就是DFS而已。

你的第二種結構父指針表，它是用來從葉子節點向根遍歷用的，同樣有許多重要的演算法需要使用它，最直接的就是判斷兩個節點的最近公共祖先，這種演算法通常還會記錄每個節點是第幾級節點，也就是到根的距離。計算最近公共祖先也就可以算出樹上的距離。在前端典型的應用，比如說子節點更新的時候，需要逐次更新父親節點上的匯總信息，這時候父指針就很有用。

這兩種結構完全是可以結合的，父親節點中保存所有子節點的列表，子節點中保存父親節點的指針或者序號，這樣就可以將這種結構通用於前兩種演算法：

[{
label: String,
id: String,
parentId: null,
children: [
{
label: String,
id: String,
parentId: String,
children: [
{
label: String,
id: String,
parentId: String
}
]
}
]
}]

allNodeIndex = {Id: node1, Id: node2, Id: node3, ...}


這並不是沒有代價的，冗餘的結構在需要進行結構修改的時候往往會將演算法複雜化。

邊表、鄰接表、鄰接矩陣是圖的存儲結構，樹是圖的特例，所以自然也可以用於樹。這些結構適用圖的相關演算法，以後也可以擴展為帶環的圖結構，比如說將來前端的樹狀圖裡，有些子節點並不是獨立的子節點，而是其他子節點的鏈接，比如說用來表示一個在兩個部門之間共享的項目之類。

使用引用還是保存ID序號這兩者沒有多大的本質區別，完全可以按照實現的難易程度來決定。帶有複雜引用的結構不能JSON序列化，比如兩個節點互相引用，這是一個缺點；但是保存ID的話，刪除節點的時候需要額外的操作來清理內存，這樣引用關係複雜的時候就要自己實現一個類似GC的演算法，而不能使用系統的GC演算法。同樣這兩種表示也很容易相互轉換，一般使用DFS一次就能完成。

用 zipper（逃

程序主要有兩個受體，有些人寫程序為了給別人看（可維護性）；有些人寫程序為了給電腦看（性能），你是哪一種呢？請對號入座

我反正屬於前者，所以我的意見是怎麼合理怎麼來，怎麼方便怎麼來，畢竟我不想被後來維護代碼的人拍死不是，follow you heart

paularmstrong/normalizr 認為在Flux和Redux中應該用扁平的數據結構，對此我個人持保留意見，所以我自己寫Redux還是reducer嵌reducer，我的理由是扁平結構的數據對程序員不夠直觀，我寧願嵌reducer，也不願意看狀態樹的時候要各種繞各種關聯id。

當然凡是無絕對，我也沒遇到過特別深的樹，如果有人跟我說他的樹經常很深（經常處理五層以上的數據），我可能還是會用扁平結構的。

基於Flux思想之外的狀態管理庫目前還沒用過，不好說。

如果將 多層嵌套對象的結構 拍平，會丟失一些信息，比如 children 中的元素如果是有順序的，拍平後這個順序如何記錄？

當然也是有辦法記錄的，需要增加一個欄位，它的值類似於 「x.y.z」這種格式 ，處理起來也不難，只是不太直觀。而 多層嵌套 結構無需這個欄位就天然能表達 順序 這個信息。

如果數據是用來渲染一顆樹的，樹結構寫在模板中，這代碼幾乎就沒法寫了，此時就非常適合使用 多層嵌套 的結構。

拍平後，有個好處是，可以根據 id 方便地查找到這個元素，如果是 多層嵌套 結構，就需要使用遞歸查找了，其實代碼也沒增加多少。

使用哪種格式，具體還是要看使用場景。

"Flat is better than nested"

- Python

一方面是數據方面的抽象，這時樹比較友好。另一種是view方向的抽象，這時拍平了比較友好。

數據量大的話，ajax懶載入，這時拍平了方便，數據量小的話，樹一口氣全載入，調用飛快。

所以還是看深度和數據量取捨吧。

哪種方便用哪種，轉化也很容易。甚至2種格式都準備著，內部的對象都是引用，占不了多少內存。