八卦樹(shù)對天量快檢索

        按我寫(xiě)的“換思路再看八卦的數”文中介紹的，將伏羲八卦的陽(yáng)爻“–”圖形看成數字1，將伏羲八卦的陰爻“- -” 圖形看成數字2時(shí)，伏羲八卦的各卦圖形對應的數為：

乾?卦為111、兌?卦為211、離?卦為121、震?卦為221、

巽?卦為122、坎?卦為212、艮?卦為122、坤?卦為222。

這種以1和2字符標識出伏羲八卦的各卦圖形的數定義為二的冪進(jìn)制數。二的冪進(jìn)制數有3個(gè)字符，分別為1、2、0。二的冪進(jìn)制數的計數規則是滿(mǎn)2的值時(shí)向上位進(jìn)1，且進(jìn)位位恢復系數為1，二的冪進(jìn)制數轉換為十進(jìn)制數時(shí)的方法與二進(jìn)制數類(lèi)同，各位的數字符號乘以數位權的和。十進(jìn)制數轉換成二的冪進(jìn)制數方法比較復雜，可在網(wǎng)上查閱我寫(xiě)的“用整數樹(shù)的研究成果  探索軟件的創(chuàng )新發(fā)展” 《軟件世界》2008年第8期中介紹的一種轉換方法。

圖1：用二的冪進(jìn)制數標識的伏羲八卦圖

一、伏羲八卦樹(shù)

    二的冪進(jìn)制數是研究伏羲八卦時(shí)，按易經(jīng)中描述的伏羲八卦是“太極生兩儀、兩儀生四象、四象生八卦、八卦生萬(wàn)物”的二分法生成卦圖顯示出的規律發(fā)現的。

             圖2：從太極二分法生成伏羲八卦圖

將圖2太極二分法生成伏羲八卦圖中的兩儀、四象、八卦中的陽(yáng)爻“–”圖形看成數字1，陰爻“- -” 圖形看成數字2替代后，可得到圖3。

   圖3：用二的冪進(jìn)制數和十進(jìn)制數標識的太極生成伏羲八卦圖

在圖3用二的冪進(jìn)制數和十進(jìn)制數標識的太極生成伏羲八卦圖中，兩儀、四象、八卦的下面標注的是對應的二的冪進(jìn)制數，上面標注的是對應的十進(jìn)制數。再將圖中兩儀、四象、八卦的各卦位置看成一個(gè)個(gè)結點(diǎn)時(shí)，伏羲八卦就是一個(gè)二叉樹(shù)。

在數據結構研究中，人們?yōu)榱丝焖贆z索數據，設定了二叉樹(shù)、B⁺樹(shù)、基數樹(shù)等許多種二叉或多叉樹(shù)，統稱(chēng)為檢索樹(shù)。檢索樹(shù)的生長(cháng)過(guò)程是：在根結點(diǎn)下有1個(gè)以上子結點(diǎn)，構成第一層子結點(diǎn)。按設定需要，第一層的各子結點(diǎn)做為父結點(diǎn)還可有1個(gè)以上子結點(diǎn)，構成第二層子結點(diǎn)……，如此，可生長(cháng)出若干層子結點(diǎn)，構成某種檢索樹(shù)。各種檢索樹(shù)的每層結點(diǎn)的個(gè)數、生長(cháng)的方式和標識等都有所不同。

圖4：二叉檢索樹(shù)圖   右側為完全二叉檢索樹(shù)

將圖3伏羲八卦的二叉樹(shù)中的太極看做二叉樹(shù)的第一層父結點(diǎn)，則與數據結構中的完全二叉檢索樹(shù)的圖形結構完全一樣，如同圖4中的右側的完全二叉檢索樹(shù)，也都有15個(gè)結點(diǎn)，也都可用于數據檢索，但是這兩個(gè)二叉樹(shù)的特征有很大不同。

二、伏羲八卦是二叉整數樹(shù)

    根據伏羲八卦生萬(wàn)物的認識，按照二分法生成規律，八卦可無(wú)限層往下分出卦。將圖3太極生八卦圖中太極看成0層，兩儀看成1層，四象看成2層，再二分可得到3層即為八卦層。將每層的各結點(diǎn)用十進(jìn)制數（不是完全二叉樹(shù)的結點(diǎn)順序號）表示該結點(diǎn)對應的二的冪進(jìn)制數值后，可得到圖5四層二叉樹(shù)。（再下分2層，就是64卦，在此不多述）

圖5：伏羲八卦二叉樹(shù)前0至4層結點(diǎn)分布圖

在圖5伏羲八卦二叉樹(shù)前0至4層結點(diǎn)分布圖中0至30十進(jìn)制整數一個(gè)不缺，一個(gè)不重復地有規律排列著(zhù)。已證明，伏羲八卦二叉樹(shù)再二分下去至N層（N為無(wú)限大正整數）時(shí)，也都有對應的整數按規律分布在各層的結點(diǎn)上。

整數有無(wú)限多是天量，伏羲八卦二叉樹(shù)也有無(wú)限多天量結點(diǎn)可使無(wú)限多天量整數有規律地排列在對應結點(diǎn)上。因此將伏羲八卦二叉樹(shù)稱(chēng)為整數二叉樹(shù)。正如整數有負整數一樣，二叉整數樹(shù)也還有以0為父結點(diǎn)的鏡像的負整數二叉樹(shù)，在此不多述。

研究整數二叉樹(shù)發(fā)現整數樹(shù)上的各結點(diǎn)的一些排列規律：

1、所有整數中的奇數都排列在根結點(diǎn)0的第一子結點(diǎn)1及它下面的分叉樹(shù)的各層結點(diǎn)上。所有整數中的偶數都排列在根結點(diǎn)0的第二子結點(diǎn)2及它下面的分叉樹(shù)的各層結點(diǎn)上。

2、整數二叉樹(shù)上所有父結點(diǎn)與其第一子結點(diǎn)的差值R=1*2ⁿ（n為父結點(diǎn)的層數），與其第二子結點(diǎn)的差值R=2*2ⁿ。

3、整數二叉樹(shù)上所有父結點(diǎn)的第一子結點(diǎn)與第二子結點(diǎn)的差值R=1*2ⁿ（n為父結點(diǎn)的層數），等等。

整數除了以二叉樹(shù)存在，還以1為差的整數一叉樹(shù)即等差數列存在，還以3至m（m為無(wú)限大正整數）叉樹(shù)存在。下圖是整數4叉樹(shù)：

圖6：整數4叉樹(shù)圖

    在數據結構中介紹有多種和多叉檢索樹(shù)。

所有檢索樹(shù)的共同特點(diǎn)是：

      1、樹(shù)結構是人為設置

      2、各層結點(diǎn)個(gè)數不固定

      3、各結點(diǎn)上的數據不固定

      4、樹(shù)的層（深度）是有限的

研究發(fā)現，所有整數樹(shù)的共同特點(diǎn)是：

      1、樹(shù)結構不是人為設置，是客觀(guān)存在

      2、各層結點(diǎn)個(gè)數固定和完整

      3、各結點(diǎn)上的數據是1個(gè)固定不變的整數

      4、樹(shù)的層（深度）是無(wú)限的

    簡(jiǎn)單說(shuō)，整數樹(shù)是客觀(guān)存在的，檢索樹(shù)是人為設定的。

三、天量數據與檢索算法

信息技術(shù)是用計算機對數據處理的技術(shù)。計算機數據處理操作主要分三步：數據輸入、數據計算、數據輸出。通常計算機的運算速度是決定數據處理速度的主要因素。但是隨著(zhù)需要處理的信息量和信息源種類(lèi)的增多，如何快速地相應提高數據輸入和數據輸出的速度也成為重要因素。在許多不匹配的信息處理中，常常計算機在等待計算數據的提供，在浪費計算資源。影響數據的輸入和輸出時(shí)間的原因是計算機的外部設備尋找數據的存取時(shí)間慢。有諸多因素造成數據的存取時(shí)間慢，其中查找數據存取地址的檢索算法優(yōu)劣是最主要因素，尤其在需處理的數據量非常大時(shí)。

人們已習慣將非常大的數據量稱(chēng)為海量數據，是可以理解的。但是，常有一些公司將他們的產(chǎn)品的處理數量宣傳為海量就不科學(xué)了。因為稱(chēng)為海的大小不一，如中南海、北海、東海等等都是不同大的。

在自然界中海是有邊界的，海量也是是有限量，只有天無(wú)邊界，可稱(chēng)為天量。目前沒(méi)有一家公司產(chǎn)品能狗快速處理天量數據。因為在迄今為止的數據結構中的隊、棧、表、圖、樹(shù)等等數據檢索的方法都是在有邊界的閉區間內的檢索的方法，即對有起始數據A和終止數據B之間的檢索；不能在開(kāi)區間，即對有起始數據A，沒(méi)有終止數據B的無(wú)限增長(cháng)的數據檢索，因為沒(méi)有發(fā)現和發(fā)明對應的數據結構。

世上有無(wú)限增長(cháng)的量嗎？有！我們天天用的數就是無(wú)限增長(cháng)的量，例如整數就是無(wú)限增長(cháng)的天量，并且所有數都源自整數。那有需要處理天量數據的應用需求嗎？有！在智慧城市中的千千萬(wàn)萬(wàn)個(gè)攝像頭在不斷產(chǎn)生的視頻信息就實(shí)天量，需要快速檢索處理。在信息化快速發(fā)展的時(shí)代，凡無(wú)邊界在增長(cháng)的數據都有必要按天量數據進(jìn)行設置和處理。否則，如按閉區間的檢索設置和處理，今后可能會(huì )有重新要設置的麻煩問(wèn)題。

    那有快速處理天量數據的檢索算法嗎？有！就是源自伏羲八卦二叉整數樹(shù)的數據結構啟發(fā)的檢索方法。

          圖7：伏羲八卦整數樹(shù)的前0至4層數據結構圖

圖7是在前面伏羲八卦二叉樹(shù)前0至4層結點(diǎn)分布圖上在每個(gè)結點(diǎn)內增加了對應該結點(diǎn)的二的冪進(jìn)制數顯示，標識的這些二的冪進(jìn)制數的值與該結點(diǎn)標識的十進(jìn)制數的值相等。

檢索技術(shù)的核心是如何快速查找出數據存取地址，為此人們研究出隊、棧、表、圖、樹(shù)等數據結構和哈希算法等多種算法。伏羲八卦整數樹(shù)能對天量數據快速檢索是基于發(fā)現了它的獨特的數據結構和在該數據結構上研究出的檢索算法。

對照圖7伏羲八卦整數樹(shù)的前0至4層數據結構圖，伏羲八卦整數樹(shù)有一些利于能對天量數據快速檢索算法的特征。歸納有：

1、伏羲八卦整數樹(shù)對應天量整數有可無(wú)限增長(cháng)的天量結點(diǎn)。

   此點(diǎn)已做說(shuō)明，不再多述。

2、伏羲八卦整數樹(shù)的層數為N（N為0至無(wú)限大正整數）。從N=1層開(kāi)始，每N層位置碼的位數等于層數N。

   例如：N=2層（四象層）的對應四象的4個(gè)二的冪進(jìn)制數都是2位。N=3層（八卦層）的對應八卦的8個(gè)二的冪進(jìn)制數都是3位。

3、伏羲八卦整數樹(shù)的各結點(diǎn)的二的冪進(jìn)制數是從0根結點(diǎn)二分法產(chǎn)生。將各結點(diǎn)的二的冪進(jìn)制數定義為該結點(diǎn)的位置碼后，可看到每個(gè)第1子結點(diǎn)的位置碼（二的冪進(jìn)制數）是在其父結點(diǎn)的位置碼前（左側）添數字1產(chǎn)生。每個(gè)第2子結點(diǎn)的位置碼是在其父結點(diǎn)的位置碼前（左側）添數字2產(chǎn)生。

    例如：N=2層（四象層）的對應的4個(gè)結點(diǎn)中，第1和第2結點(diǎn)的位置碼是在它們的父結點(diǎn)1的位置碼前分別添上1和2產(chǎn)生（左分叉添1，右分叉添2），即為11、21。第3和第4結點(diǎn)的位置碼同樣是在它們的父結點(diǎn)2的位置碼前分別添上1和2（左分叉添1，右分叉添2）產(chǎn)生，即為12、22。

4、伏羲八卦整數樹(shù)的結點(diǎn)是二分發(fā)產(chǎn)生的，每個(gè)結點(diǎn)的位置碼都據有遺傳基因，可向上查到該結點(diǎn)的父結點(diǎn)至根結點(diǎn)位置碼，也可下推算出該結點(diǎn)的兩個(gè)子結點(diǎn)位置碼和這兩個(gè)子結點(diǎn)的所有無(wú)限多的的各層子結點(diǎn)的位置碼。

例如;在伏羲八卦整數樹(shù)的前0至4層數據結構圖中選N=3層中間結點(diǎn)數為8的結點(diǎn)，該結點(diǎn)的位置碼是112。從這個(gè)結點(diǎn)的位置碼112可看出后兩位12是該結點(diǎn)的父結點(diǎn)的12的位置碼。還可看到這個(gè)結點(diǎn)的位置碼112的最后位2是該結點(diǎn)的父結點(diǎn)的12的父結點(diǎn)2的位置碼。

在這個(gè)該結點(diǎn)數為8的結點(diǎn)位置碼112上按照伏羲八卦整數樹(shù)的子結點(diǎn)位置碼二分發(fā)產(chǎn)生規則，首先在該結點(diǎn)位置碼112前（左側）添上1產(chǎn)生該結點(diǎn)的第一子結點(diǎn)位置碼1112。再在該結點(diǎn)位置碼112前（左側）添上2產(chǎn)生該結點(diǎn)的第二子結點(diǎn)位置碼2112。用同樣的規則還可很容易下推算出這兩個(gè)子結點(diǎn)的所有無(wú)限多的的各層子結點(diǎn)的位置碼。

5、因的各結點(diǎn)的位置碼就是該結點(diǎn)的二的冪進(jìn)制數，也就是各結點(diǎn)的位置碼的值等于該結點(diǎn)十進(jìn)制整數值。這是伏羲八卦整數樹(shù)數據結構優(yōu)于所有人為設計的數據結構的特性。伏羲八卦整數樹(shù)可檢索天量數據，且數據存取地址數不用查找和計算，直接等于唯一對應整數。

在伏羲八卦整數樹(shù)僅發(fā)現的這5種數據結構特性，就可得到多種對天量數據快速檢索的算法。

簡(jiǎn)單舉例：將某一需存取的數據，如不是整數，轉換為整數后假設為十進(jìn)制數24，再將24轉換為對應的為2112，也就是在伏羲八卦整數樹(shù)上的存取位置碼，按該位置碼可有以下查找算法供參考：（請參照圖7）

算法1：因十進(jìn)制數24的二的冪進(jìn)制數為2112是4位數，按在伏羲八卦整數樹(shù)的存取結點(diǎn)的二的冪進(jìn)制數與該結點(diǎn)位置碼相同，且位數等于層數N的特性，直接在N=4層結點(diǎn)中順序查找或設計一個(gè)算法查找。在本例中，十進(jìn)制數24的存取位置可快速查出在N=4層的第10個(gè)結點(diǎn)。

算法2：根據伏羲八卦整數樹(shù)的各結點(diǎn)對應的二的冪進(jìn)制數（位置碼）據有遺傳基因特性，在已知十進(jìn)制數24的二的冪進(jìn)制數（位置碼）為2112時(shí)，將24的二的冪進(jìn)制數（位置碼）2112最右側位值2為一個(gè)位置碼，在伏羲八卦整數樹(shù)的N=1層查到對應結點(diǎn)2為起始結點(diǎn)，再依據24的二的冪進(jìn)制數（位置碼）2112右側第二位是1向左下側查到12結點(diǎn)，然后再依據24的二的冪進(jìn)制數（位置碼）2112右側第二位是1向左下側查到112結點(diǎn)，最后再依據24的二的冪進(jìn)制數（位置碼）2112右側第3三位是2向右下側查到2112結點(diǎn)，用4步就查到十進(jìn)制數24的存取位置2112結點(diǎn)。

以上介紹的是利用伏羲八卦整數樹(shù)快速檢索天量數據的原理和簡(jiǎn)單檢索算法，希望能給大家一個(gè)啟發(fā)。感興趣的人士可在網(wǎng)上查閱我寫(xiě)的“整數樹(shù)結構與天量數據快速檢索”一文，做更多的了解，在進(jìn)行更深入的研究后，發(fā)明出更新的信息技術(shù)。