本文為來自 字節跳動-國際化電商-S項目 的文章，已授權 ELab 發布。
背景本人自己曾經造輪子搞過一個 Node.js 端的應用層 Web 框架，裡面涉及到一個路由系統的實現，當時是通過一個叫前綴樹的數據結構來實現便捷的路由查找與匹配機制，這裡跟大家分享一下。
前綴樹介紹前綴樹，即字典樹，又稱 Trie 樹。這種數據結構通常用來儲存字符串，並且是以路徑字符節點的形式來儲存。擁有公共前綴的字符串，會共享同樣的父節點路徑。前綴樹是通過利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
前綴樹的 3 個基本性質：
每個節點的所有子節點包含的字符都不相同。
這個問題是在做 Web 框架的路由時碰見的，所以這裡的請求路徑的形式可以當做就是一個個 URL 刨去協議名、域名、端口號（有的話）之後的部分，一般是通過斜槓 ("/") 來鏈接一個個元素，形如：
而且在大部分時候，路由的路徑是根據模塊的層級來劃分功能，以達到顧名思義的目的，因此路由的路徑其實是會有很多公共的前綴。比如，上述例子中同屬於一個二級模塊 User 的接口：
/api/user/list 和 /api/user/create ，它們便有共同的前綴 /api/user ，聯繫到上述前綴樹的性質，我們便可以通過前綴樹來儲存和搜索這些路由信息。
應用到路由匹配中根據上面的一個結論，可以得到一個基本思路：
把路由路徑當做是用斜槓連接起來的 Component 的組合，因此前綴樹當中的節點，儲存的就不再是單個字符，而是一個個 Component，但這不會影響我們去使用這種數據結構來進行搜索。
按照上面的描述，將這兩串路徑用 / 分割，形成一組 Component，同時它們擁有兩層的公共路徑，那麼將會形成這樣的樹結構：（葉子節點儲存的是對應的 handler）
將路由聲明添加到 Trie 樹中下面是將路由聲明的 Component 添加到 Trie 樹中的代碼：
router.get( '/api/user/nameList', xxx);
addToTree(urlPattern:string,handler:any){letp=this.root;//Paddinganelementtotherearofthearraytomaketheleafnode.consturlPatternComponents=[...urlPattern.split('/').filter(Boolean),LEAF_SIGN];urlPatternComponents.forEach(component=>{const{quickMap}=p;//IfquickMaphasthiscomponent,itmeanstheroutehasthesamenamespace//withexistedroute,sogettothenextleveldirectly.Ifthenodeisaleaf//node,justreturncauseitmeansredundantrouteisaddingtothetree,wedontneedit.if(p.quickMap.has(componentasstring)){constnode=p.quickMap.get(componentasstring)!;if(isLeafNode(node)){return;}p=node;return;}if(component===LEAF_SIGN){constnewNode=newRouterTreeLeafNode(handler);quickMap.set(LEAF_SIGN,newNode);return;}constnewNode=newNTreeNode(componentasstring);p.quickMap.set(componentasstring,newNode);//Whentheexpressionlike':id'showsintheroute,itshould//treatitasaparameternode.Onetreenodecanonlyhaveoneparameternode.if((componentasstring).indexOf(':')>-1){p.paramNode=newNode;}p=newNode;});}router.get(' /api/hi/:name'
這裡用一個 quickMap 來儲存子節點，key 為 Component，value 為節點，用於在匹配過程中快速查找到與 Component 值相匹配的節點。注意在 urlComponents 數組末尾填充了一個叫 LEAF_SIGN 的 Symbol，看上面的樹結構圖就知道，實際路由聲明的 Component 遍歷完之後，葉子節點的值儲存的是最後一個 Component，因此我們需要給它添加一個子節點，用來儲存實際匹配的結果，也就是路由的 Handler。paramNode 放到動態路由匹配一節再解析，這裡可以先不管。
靜態路由匹配在匹配時，也實際的請求路徑同樣按照上面的分割方式切分成一組 Component，從 Trie 的根節點開始，它的子節點必定只有一個，將指針指向它的唯一子節點，並將遍歷 Component 的指針往後挪，根據遍歷到的新的 Component 去匹配下一層的子節點。直到 Component 被遍歷完，若最後可以找到相匹配的子節點，則該節點為葉子節點，將其值取出作為結果返回。若未能匹配，在靜態路由匹配的情況中就是 Route not found 的情況了，但是實際場景肯定沒有這麼簡單粗暴，這裡先留個坑，後面會講到。
代碼如下：
getHandlerFromTree(url:string):any{const[urlWithParams,_]=url.split('?');consturlComponents=urlWithParams.split('/').filter(Boolean);letp=this.root;leti=0;letres;letpath='';while(p){constcomponent=urlComponents[i++];//IfthequickMaphasthecomponent,returnitifit'salsoaleafnode.//Orjustmovetothenextlevelandstorethepath.if(p.quickMap.has(component)){constnode=p.quickMap.get(component)!;if(isLeafNode(node)){res=node.value;break;}path+='/'+node.value;p=node;continue;}constleafNode=p.quickMap.get(LEAF_SIGN);if(leafNode==null){//IfquickMaphasothernode,itmeansstaticroutecannotbematched.if(p.quickMap.size>0){consterr={message:'Routenotdefined',statusCode:404,statusMessage:'Notfound'};throwerr;}//Elseitmeansnohandlerwasdefined.consterr={message:'Handlernotdefined',statusCode:500,statusMessage:'Notfound'};throwerr;}res=leafNode.value;break;}return{handler:res,path};}動態路由匹配我們在使用 Express 或是 Koa.js 時，會用到形如 /api/user/:id 這樣的動態路由聲明，這是一個實用的功能，來看下如何在基於 Trie 樹的路由系統中實現動態路由。
還是剛才的兩條路由聲明，現在我們加上一條新的:
/api/user/nameList
/api/user/addressList
/api/user/:id
得到這樣的結構:
對這樣的動態參數路由聲明，將其作為一個特殊節點，用一個單獨的指針 paramNode 保存，我們限制一種路由聲明只能有一個動態參數，就是不能既有 /api/user/:id 又有 /api/user/:name，這樣的話在實際匹配時無法得知，路徑中對應位置的 Component 代表的是什麼含義。
接上面的坑，實際匹配時，當碰見無法匹配的 Component 時，那麼代表這個 Component 是一個動態參數的實際值，所以無法跟任何靜態聲明匹配，這時就直接去找該節點的 paramNode 指針指向的節點，也就是說當碰到這種情況時，我們直接把它歸類為動態參數匹配的場景。
看一下加入動態參數匹配的代碼，省略共同部分：
getHandlerFromTree(url:string):any{//...if(p.quickMap.has(component)){constnode=p.quickMap.get(component)!;if(isLeafNode(node)){res=node.value;break;}path+='/'+node.value;p=node;continue;}if(component){path+='/'+p.paramNode.value;p=p.paramNode;continue;}constleafNode=p.quickMap.get(LEAF_SIGN);//...}那麼這時又有一個坑，如果 paramNode 不存在，該怎麼辦？下面來說下一種場景：正則表達式匹配。
正則表達式匹配router.get( /hi/all/ , xxx)
因為正則表達式是可以直接進行字符串匹配的，所以這種路由聲明將會脫離 Trie 樹的數據結構特點而存在，我們選擇將這種節點全部儲存在根結點下方，避免不必要的查找。上面說到，如果一個節點的 paramNode 指針不存在，那麼我們只好做最後一種選擇，將整個路徑進行正則表達式匹配，如果仍然無法匹配，就只好拋出路由未找到的異常，由依賴路由的代碼去處理這個異常。
getHandlerFromTree(url:string){//...if(component){//Ifnoparameternodefound,tryregularexpressionmatching.if(!p.paramNode){const{handler,matched}=this.getHandlerFromRegExpNode(url);res=handlerpath=matched;break;}path+='/'+p.paramNode.value;p=p.paramNode;continue;}constleafNode=p.quickMap.get(LEAF_SIGN);//...}添加正則表達式節點到樹中：
addRegExpToTree(urlPattern:RegExp,handler:Function){constroot=this.root;root.children.push(newRouterRegExpLeafNode(urlPattern,handler));}得到的結構是這樣的：
這樣就實現了一個支持靜態、動態、正則表達式三種匹配方式的路由機制。
簡單分析使用 Trie 樹來做路由匹配就是比較折中的方案，通常來說路由聲明都會按照模塊來做分類，在同一個一級模塊下面的多個二級模塊路由，然後每個二級模塊下面會有多個三級模塊路由，就會產生公共前綴，就給了 Trie 樹節省空間的機會，並且重複率越高節省的空間越多（聽起來怎麼像 gzip 壓縮），Trie 樹的最壞查找效率取決於所儲存的序列的最長長度，也就是樹的最大深度，是一個線性級別的時間複雜度。這裡會有另一個問題，如果所有路由聲明都是分散的，沒有公共前綴，假設有 m 條長度為 n 的記錄，在彼此沒有公共前綴時，Trie 樹的空間複雜度會達到 O(mn)，故在使用時應儘量收斂路由聲明的 namespace 數量。
總結一開始內心有個問題，為什麼不直接用哈希表儲存靜態路由，然後動態路由就使用遍歷查找的方式？後面對這個問題有了一些自己的理解：
使用哈希表儲存靜態路由，查找速度是常數級別的，非常快，但是需要線性空間來儲存，而且每一條靜態路由都需要完整儲存，那麼就浪費了公共前綴這個特性。其次，對動態路由使用遍歷匹配的方式太過暴力，動態路由沒有辦法去很好地做緩存，而路由匹配是個高頻的動作，這種方式的性能開銷相對來說比較大，也是不夠合適的。
代碼倉庫https://github.com/divasatanica/auf/blob/main/packages/core/src/router/prefix-tree/index.ts
有興趣的小夥伴可以去瞅瞅。
❤️ 謝謝支持以上便是本次分享的全部內容，希望對你有所幫助^_^
喜歡的話別忘了 分享、點讚、收藏 三連哦~。
歡迎關注公眾號 ELab團隊 收貨大廠一手好文章~
可憑內推碼投遞 字節跳動-國際化電商-S項目 團隊 相關崗位哦~
- END -
留言列表