在去年的軟件開發(fā)2.0技術(shù)大會(huì)上，我講了一個(gè)支持動(dòng)態(tài)負(fù)載均衡的多核查找設(shè)計(jì)方法?；舅枷胧遣捎脭?shù)據(jù)結(jié)構(gòu)分拆的方法，使用了多級(jí)的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。下面先簡(jiǎn)要介紹一下這種多級(jí)數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)思路，然后給出一個(gè)采用數(shù)組順序查找作為查找表實(shí)現(xiàn)的多級(jí)數(shù)據(jù)結(jié)構(gòu)類CDHashArray。

在CDHashArray中，對(duì)數(shù)組的插入和刪除都是順序化的操作，查找也是近似于順序化的操作，看起來(lái)似乎會(huì)很慢。實(shí)際上對(duì)于小數(shù)組，比如只有幾個(gè)或十來(lái)個(gè)數(shù)組，其效率并不慢，這使得以前在單核時(shí)代無(wú)法用于大型查找的數(shù)組順序查找，在多核時(shí)代卻可以得到很好應(yīng)用前景。

二級(jí)查找結(jié)構(gòu)基本思想

要了解多級(jí)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，首先得知道基本的二級(jí)查找數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)思想。

二級(jí)查找結(jié)構(gòu)就是在第1級(jí)查找時(shí)找到二級(jí)子表的位置，然后在找到的二級(jí)子表中進(jìn)行第二次查找來(lái)找到對(duì)應(yīng)的目標(biāo)數(shù)據(jù)。

典型的二級(jí)查找結(jié)構(gòu)示意圖如下：

圖 16.2.1: 二級(jí)查找結(jié)構(gòu)示意圖

二級(jí)查找結(jié)構(gòu)由一級(jí)查找表和二級(jí)子表構(gòu)成，一個(gè)查找表中的每個(gè)節(jié)點(diǎn)指向一個(gè)二級(jí)查找子表。查找時(shí)，先將關(guān)鍵詞映射成一級(jí)查找表的位置，然后將對(duì)應(yīng)位置的二級(jí)子表取出，在子表中找到對(duì)應(yīng)的查找目標(biāo)數(shù)據(jù)。

Intel Threading Building Blocks(TBB)開源項(xiàng)目中，其中的concurrent_hash_map使用的就是一種最簡(jiǎn)單的二級(jí)查找結(jié)構(gòu)。它使用了哈希表式的數(shù)據(jù)結(jié)構(gòu)，并給哈希表的每個(gè)桶設(shè)一把鎖。

對(duì)于普通的查找，這種簡(jiǎn)單的二級(jí)查找結(jié)構(gòu)也許夠用了，但是對(duì)于一些大型的查找，這種簡(jiǎn)單的二級(jí)查找結(jié)構(gòu)并不能滿足。首先的問(wèn)題是如果子表數(shù)量過(guò)多，則鎖的數(shù)量也非常多，鎖本身需要占用大量的內(nèi)存開銷。

如 果子表數(shù)量過(guò)少，那么又會(huì)引起另外一個(gè)重要的問(wèn)題，那就是負(fù)載平衡問(wèn)題。因?yàn)檫@種情況中有可能各個(gè)二級(jí)子表中的數(shù)據(jù)數(shù)量相差非常大，這將導(dǎo)致某些子表的訪 問(wèn)量很少，而某些子表的訪問(wèn)量很大。這些訪問(wèn)量大的表很容易發(fā)生多個(gè)線程同時(shí)訪問(wèn)的情況，從而導(dǎo)致集中式鎖競(jìng)爭(zhēng)情況的發(fā)生。

為了解決二級(jí)查找結(jié)構(gòu)中的不足，下面來(lái)看看多級(jí)查找結(jié)構(gòu)的設(shè)計(jì)思想。

多級(jí)查找結(jié)構(gòu)設(shè)計(jì)思想

多級(jí)查找結(jié)構(gòu)是在二級(jí)查找結(jié)構(gòu)的基礎(chǔ)上設(shè)計(jì)的，當(dāng)某個(gè)子表中數(shù)據(jù)個(gè)數(shù)過(guò)多時(shí)，可以將其拆分成兩個(gè)或更多個(gè)子表，同時(shí)新建一個(gè)索引表來(lái)指向這幾個(gè)拆分候的子表，指向原來(lái)子表的指針指向新建的索引表。

如果拆分后的子表內(nèi)插入的數(shù)據(jù)過(guò)多時(shí)，可以繼續(xù)將其分拆，這樣一直分拆下去，將形成一個(gè)多級(jí)的查找數(shù)據(jù)結(jié)構(gòu)，下圖就是一個(gè)多級(jí)查找結(jié)構(gòu)示意圖。