前綴樹在前端路由系統(tǒng)中的應(yīng)用
大廠技術(shù) 堅持周更 精選好文
背景
本人自己曾經(jīng)造輪子搞過一個 Node.js 端的應(yīng)用層 Web 框架，里面涉及到一個路由系統(tǒng)的實現(xiàn)，當(dāng)時是通過一個叫前綴樹的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)便捷的路由查找與匹配機制，這里跟大家分享一下。
前綴樹介紹
前綴樹，即字典樹，又稱 Trie 樹。這種數(shù)據(jù)結(jié)構(gòu)通常用來儲存字符串，并且是以路徑字符節(jié)點的形式來儲存。擁有公共前綴的字符串，會共享同樣的父節(jié)點路徑。前綴樹是通過利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。
前綴樹的 3 個基本性質(zhì)：
根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。 從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。 每個節(jié)點的所有子節(jié)點包含的字符都不相同。
路由匹配的場景
這個問題是在做 Web 框架的路由時碰見的，所以這里的請求路徑的形式可以當(dāng)做就是一個個 URL 刨去協(xié)議名、域名、端口號（有的話）之后的部分，一般是通過斜杠 ("/") 來鏈接一個個元素，形如：
/api/user/nameList /api/user/addressList
而且在大部分時候，路由的路徑是根據(jù)模塊的層級來劃分功能，以達到顧名思義的目的，因此路由的路徑其實是會有很多公共的前綴。比如，上述例子中同屬于一個二級模塊 User 的接口：
/api/user/list 和 /api/user/create ，它們便有共同的前綴 /api/user ，聯(lián)系到上述前綴樹的性質(zhì)，我們便可以通過前綴樹來儲存和搜索這些路由信息。
應(yīng)用到路由匹配中
根據(jù)上面的一個結(jié)論，可以得到一個基本思路：
把路由路徑當(dāng)做是用斜杠連接起來的 Component 的組合，因此前綴樹當(dāng)中的節(jié)點，儲存的就不再是單個字符，而是一個個 Component，但這不會影響我們?nèi)ナ褂眠@種數(shù)據(jù)結(jié)構(gòu)來進行搜索。
按照上面的描述，將這兩串路徑用 / 分割，形成一組 Component，同時它們擁有兩層的公共路徑，那么將會形成這樣的樹結(jié)構(gòu)：（葉子節(jié)點儲存的是對應(yīng)的 handler）
將路由聲明添加到 Trie 樹中
下面是將路由聲明的 Component 添加到 Trie 樹中的代碼：
router.get( '/api/user/nameList', xxx);
addToTree(urlPattern: string, handler: any) {
let p = this.root;
// Padding an element to the rear of the array to make the leaf node.
const urlPatternComponents = [...urlPattern.split('/').filter(Boolean), LEAF_SIGN];
urlPatternComponents.forEach(component => {
const { quickMap } = p;
// If quickMap has this component, it means the route has the same namespace
// with existed route, so get to the next level directly. If the node is a leaf
// node, just return cause it means redundant route is adding to the tree, we dont need it.
if (p.quickMap.has(component as string)) {
const node = p.quickMap.get(component as string)!;
if (isLeafNode(node)) {
return;
}
p = node;
return;
}
if (component === LEAF_SIGN) {
const newNode = new RouterTreeLeafNode(handler);
quickMap.set(LEAF_SIGN, newNode);
return;
}
const newNode = new NTreeNode(component as string);
p.quickMap.set(component as string, newNode);
// When the expression like ':id' shows in the route, it should
// treat it as a parameter node.One tree node can only have one parameter node.
if ((component as string).indexOf(':') > -1) {
p.paramNode = newNode;
}
p = newNode;
});
}
router.get(' /api/hi/:name'
這里用一個 quickMap 來儲存子節(jié)點，key 為 Component，value 為節(jié)點，用于在匹配過程中快速查找到與 Component 值相匹配的節(jié)點。注意在 urlComponents 數(shù)組末尾填充了一個叫 LEAF_SIGN 的 Symbol，看上面的樹結(jié)構(gòu)圖就知道，實際路由聲明的 Component 遍歷完之后，葉子節(jié)點的值儲存的是最后一個 Component，因此我們需要給它添加一個子節(jié)點，用來儲存實際匹配的結(jié)果，也就是路由的 Handler。paramNode 放到動態(tài)路由匹配一節(jié)再解析，這里可以先不管。
靜態(tài)路由匹配
在匹配時，也實際的請求路徑同樣按照上面的分割方式切分成一組 Component，從 Trie 的根節(jié)點開始，它的子節(jié)點必定只有一個，將指針指向它的唯一子節(jié)點，并將遍歷 Component 的指針往后挪，根據(jù)遍歷到的新的 Component 去匹配下一層的子節(jié)點。直到 Component 被遍歷完，若最后可以找到相匹配的子節(jié)點，則該節(jié)點為葉子節(jié)點，將其值取出作為結(jié)果返回。若未能匹配，在靜態(tài)路由匹配的情況中就是 Route not found 的情況了，但是實際場景肯定沒有這么簡單粗暴，這里先留個坑，后面會講到。
代碼如下：
getHandlerFromTree(url: string): any{
const [urlWithParams, _] = url.split('?');
const urlComponents = urlWithParams.split('/').filter(Boolean);
let p = this.root;
let i = 0;
let res;
let path = '';
while (p) {
const component = urlComponents[i ++];
// If the quickMap has the component, return it if it's also a leaf node.
// Or just move to the next level and store the path.
if (p.quickMap.has(component)) {
const node = p.quickMap.get(component)!;
if (isLeafNode(node)) {
res = node.value;
break;
}
path += '/' + node.value;
p = node;
continue;
}
const leafNode = p.quickMap.get(LEAF_SIGN);
if (leafNode == null) {
// If quickMap has other node, it means static route cannot be matched.
if (p.quickMap.size > 0) {
const err = { message: 'Route not defined', statusCode: 404, statusMessage: 'Not found' };
throw err;
}
// Else it means no handler was defined.
const err = { message: 'Handler not defined', statusCode: 500, statusMessage: 'Not found' };
throw err;
}
res = leafNode.value;
break;
}
return {
handler: res,
path
};
}
動態(tài)路由匹配
我們在使用 Express 或是 Koa.js 時，會用到形如 /api/user/:id 這樣的動態(tài)路由聲明，這是一個實用的功能，來看下如何在基于 Trie 樹的路由系統(tǒng)中實現(xiàn)動態(tài)路由。
還是剛才的兩條路由聲明，現(xiàn)在我們加上一條新的:
/api/user/nameList
/api/user/addressList
/api/user/:id
得到這樣的結(jié)構(gòu):
對這樣的動態(tài)參數(shù)路由聲明，將其作為一個特殊節(jié)點，用一個單獨的指針 paramNode 保存，我們限制一種路由聲明只能有一個動態(tài)參數(shù)，就是不能既有 /api/user/:id 又有 /api/user/:name，這樣的話在實際匹配時無法得知，路徑中對應(yīng)位置的 Component 代表的是什么含義。
接上面的坑，實際匹配時，當(dāng)碰見無法匹配的 Component 時，那么代表這個 Component 是一個動態(tài)參數(shù)的實際值，所以無法跟任何靜態(tài)聲明匹配，這時就直接去找該節(jié)點的 paramNode 指針指向的節(jié)點，也就是說當(dāng)碰到這種情況時，我們直接把它歸類為動態(tài)參數(shù)匹配的場景。
看一下加入動態(tài)參數(shù)匹配的代碼，省略共同部分：
getHandlerFromTree(url: string): any {
// ...
if (p.quickMap.has(component)) {
const node = 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;
}
const leafNode = p.quickMap.get(LEAF_SIGN);
// ...
}
那么這時又有一個坑，如果 paramNode 不存在，該怎么辦？下面來說下一種場景：正則表達式匹配。
正則表達式匹配
router.get( /hi/all/ , xxx)
因為正則表達式是可以直接進行字符串匹配的，所以這種路由聲明將會脫離 Trie 樹的數(shù)據(jù)結(jié)構(gòu)特點而存在，我們選擇將這種節(jié)點全部儲存在根結(jié)點下方，避免不必要的查找。上面說到，如果一個節(jié)點的 paramNode 指針不存在，那么我們只好做最后一種選擇，將整個路徑進行正則表達式匹配，如果仍然無法匹配，就只好拋出路由未找到的異常，由依賴路由的代碼去處理這個異常。
getHandlerFromTree(url: string) {
// ...
if (component) {
// If no parameter node found, try regular expression matching.
if (!p. paramNode ) {
const { handler, matched } = this . getHandlerFromRegExpNode (url);
res = handler
path = matched;
break ;
}
path += '/' + p.paramNode.value;
p = p.paramNode;
continue;
}
const leafNode = p.quickMap.get(LEAF_SIGN);
// ...
}
添加正則表達式節(jié)點到樹中：
addRegExpToTree(urlPattern: RegExp, handler: Function) {
const root = this.root;
root.children.push(new RouterRegExpLeafNode(urlPattern, handler));
}
得到的結(jié)構(gòu)是這樣的：
這樣就實現(xiàn)了一個支持靜態(tài)、動態(tài)、正則表達式三種匹配方式的路由機制。
簡單分析
使用 Trie 樹來做路由匹配就是比較折中的方案，通常來說路由聲明都會按照模塊來做分類，在同一個一級模塊下面的多個二級模塊路由，然后每個二級模塊下面會有多個三級模塊路由，就會產(chǎn)生公共前綴，就給了 Trie 樹節(jié)省空間的機會，并且重復(fù)率越高節(jié)省的空間越多（聽起來怎么像 gzip 壓縮），Trie 樹的最壞查找效率取決于所儲存的序列的最長長度，也就是樹的最大深度，是一個線性級別的時間復(fù)雜度。這里會有另一個問題，如果所有路由聲明都是分散的，沒有公共前綴，假設(shè)有 m 條長度為 n 的記錄，在彼此沒有公共前綴時，Trie 樹的空間復(fù)雜度會達到 O(mn)，故在使用時應(yīng)盡量收斂路由聲明的 namespace 數(shù)量。
總結(jié)
一開始內(nèi)心有個問題，為什么不直接用哈希表儲存靜態(tài)路由，然后動態(tài)路由就使用遍歷查找的方式？后面對這個問題有了一些自己的理解：
使用哈希表儲存靜態(tài)路由，查找速度是常數(shù)級別的，非?？欤切枰€性空間來儲存，而且每一條靜態(tài)路由都需要完整儲存，那么就浪費了公共前綴這個特性。其次，對動態(tài)路由使用遍歷匹配的方式太過暴力，動態(tài)路由沒有辦法去很好地做緩存，而路由匹配是個高頻的動作，這種方式的性能開銷相對來說比較大，也是不夠合適的。
代碼倉庫
https://github.com/divasatanica/auf/blob/main/packages/core/src/router/prefix-tree/index.ts
有興趣的小伙伴可以去瞅瞅。
?? 謝謝支持
以上便是本次分享的全部內(nèi)容，希望對你有所幫助^_^
喜歡的話別忘了 分享、點贊、收藏 三連哦~。
歡迎關(guān)注公眾號 趣談前端 收貨大廠一手好文章~
點個在看你最好看