鍍金池/ 問答/Java  PHP  Python  GO/ 大二叉樹遍歷某一個(gè)節(jié)點(diǎn)下的所有子孫節(jié)點(diǎn)？

大二叉樹遍歷某一個(gè)節(jié)點(diǎn)下的所有子孫節(jié)點(diǎn)？

一個(gè)大的二叉樹，樹層級是不確定，現(xiàn)在要實(shí)現(xiàn)這么幾個(gè)需求：
1.記錄層級關(guān)系。比如：給你一個(gè)節(jié)點(diǎn)id：9，需要查詢出這個(gè)節(jié)點(diǎn)下的兒子或者孫子，或者....或者所有子孫節(jié)點(diǎn)
2.還要一下查詢統(tǒng)計(jì)需求

對于需求1，我這邊是講節(jié)點(diǎn)id存儲到redis里面，結(jié)構(gòu)是zset, key是節(jié)點(diǎn)id，score是層級關(guān)系，如果是兒子節(jié)點(diǎn)，score就是-1，孫子就是-2，以此內(nèi)推。。層級無限，有可能很多層。越往后的score越小。

但是這樣存儲有一個(gè)問題，就是查詢統(tǒng)計(jì)需求就不太好弄了，比如，我需要查詢出某個(gè)節(jié)點(diǎn)下的所有當(dāng)天新增的節(jié)點(diǎn)。這類需求，目前我想到的就是從redis拿到當(dāng)前節(jié)點(diǎn)下的所有子孫節(jié)點(diǎn)id，然后通過id去數(shù)據(jù)庫里面通過in過濾出當(dāng)天的新增節(jié)點(diǎn)，這樣有一個(gè)問題，就是如果子孫節(jié)點(diǎn)太多，in查詢效率非常低，服務(wù)會掛。

不知道大家誰有沒有好一點(diǎn)的方案？目前在研究Neo4j,這個(gè)圖形數(shù)據(jù)庫，不知道能不能實(shí)現(xiàn)這樣的需求？有大神使用過嗎？

回答
編輯回答
陌如玉

你存儲二叉樹的這個(gè)方法沒什么問題。你說從redis拿到了所有的子孫節(jié)點(diǎn)的id，然后去數(shù)據(jù)庫用in過濾當(dāng)天的新增節(jié)點(diǎn)。是這樣嗎? select * from tab where id in (ids) and date =sysdate; 那么就是如果子孫節(jié)點(diǎn)很多，這個(gè)ids就會非常大。我不知道你是不是想這個(gè)樣。但是你現(xiàn)在存在redis的id和score都可以做關(guān)系型數(shù)據(jù)庫的索引（id相當(dāng)于主鍵，distinct（score）最大是2），所以沒必要存在非得用redis。再針對業(yè)務(wù)中經(jīng)常出現(xiàn)的查詢條件做一下hash，比如這個(gè)日期就可以。如果每天新增的數(shù)據(jù)量很多的話甚至可以做一下分表。

2018年8月6日 11:10
編輯回答
還吻

你的需求看不出要用redis的理由，可以簡單的使用關(guān)系型數(shù)據(jù)庫實(shí)現(xiàn)樹形層級關(guān)系，使用某個(gè)字段保存父子路徑關(guān)系。比如 root 1 , 有兩個(gè)節(jié)點(diǎn) , 1-2-,1-3-; 2，3又有兒子節(jié)點(diǎn) 1-2-4-,1-3-5-,那么統(tǒng)計(jì)只要簡單的like 就可以方便的拿到本節(jié)點(diǎn)的所有子孫節(jié)點(diǎn)，比如查詢 path like '1-%',即為拿到id=1的所有子孫節(jié)點(diǎn)，path like '1-2-%'即為拿到id=2的所有子孫節(jié)點(diǎn)。

2018年8月16日 23:38