趙林斌 邵戰(zhàn)強(qiáng) 魏 威

（渭南市互聯(lián)網(wǎng)信息辦公室，陜西 渭南 714000）

渭南智慧城市大數(shù)據(jù)基礎(chǔ)平臺(tái)的建設(shè)完成，解決了目前渭南市大部分政府部門各異構(gòu)系統(tǒng)之間的數(shù)據(jù)整合，實(shí)現(xiàn)渭南市各部門原有各業(yè)務(wù)系統(tǒng)數(shù)據(jù)級(jí)集成，通過平臺(tái)內(nèi)部數(shù)據(jù)驅(qū)動(dòng)引擎，實(shí)現(xiàn)不同單位或系統(tǒng)間的信息整合、交換、共享和業(yè)務(wù)協(xié)同與查詢，為各部門提供統(tǒng)一、標(biāo)準(zhǔn)的服務(wù)接口，保證異構(gòu)數(shù)據(jù)庫之間的數(shù)據(jù)交換與共享。但是由于平臺(tái)接入的部門越來越多，不同部門間數(shù)據(jù)存在著交叉關(guān)聯(lián)，導(dǎo)致業(yè)務(wù)量與數(shù)據(jù)量激增，最終導(dǎo)致信息搜索效率下降。為了保證平臺(tái)的高速運(yùn)轉(zhuǎn)與用戶體驗(yàn)，應(yīng)構(gòu)建一種高效的查詢體系，解決平臺(tái)海量數(shù)據(jù)的查詢速率下降的問題。

因此，本文提出一種基于二分法的海量數(shù)據(jù)快速查詢技術(shù)。再對(duì)搜索過程通過借助二分法對(duì)搜索算法進(jìn)行改進(jìn)，最終得到最佳的搜索解區(qū)域，提高搜索的效率，保證平臺(tái)系統(tǒng)的運(yùn)轉(zhuǎn)高速性。

1 海量數(shù)據(jù)的快速二分法查詢

1.1 二分法快速查詢理論

通常采用的數(shù)據(jù)查詢方法需要對(duì)所有數(shù)據(jù)進(jìn)行。效率低下且占用服務(wù)器資源。而對(duì)于用戶來說，這不僅降低了工作效率，用戶體驗(yàn)也極差。結(jié)合渭南客戶實(shí)際情況，對(duì)當(dāng)前查詢技術(shù)進(jìn)行分析，從局部并行查詢、查詢?nèi)诤蟽蓚€(gè)方面分析問題鎖所在。決定使用二分定位，解決數(shù)據(jù)排序、整合等影響查詢效率的問題。

平臺(tái)優(yōu)化的查詢方法基于一種經(jīng)典的數(shù)據(jù)搜索算法——二分法。首先需要根據(jù)相關(guān)信息確定其根區(qū)間，然后將區(qū)間分成兩個(gè)相等的部分，再通過對(duì)函數(shù)f（x）符號(hào)和單調(diào)性進(jìn)行判斷分析，使根區(qū)間逐漸減小。在根區(qū)間在所尋求的范圍內(nèi)，可以快速找到滿足需求的近似根。在此以有序數(shù)組Array[N0，N1，...，Nn]為例，主要步驟如下：

確定數(shù)組的中位數(shù)為：M=[N0，N1，...，Nn]/2。然后比較目標(biāo)查詢數(shù)據(jù)Nm與中位數(shù)M的大小，如果兩值相等，則返回此位置； 否則，對(duì)下一個(gè)新的區(qū)間繼續(xù)進(jìn)行上述步驟。若M小于Nm，結(jié)合數(shù)組有序性，則Nm＜M=[M，...，Nn]，因此，對(duì)下一個(gè)搜索區(qū)間Array[N0，N1，...，M]繼續(xù)進(jìn)行上述操作。每一次搜索與中值進(jìn)行比較，確定搜索結(jié)果后再進(jìn)行判斷。若搜索不成功，則將搜索區(qū)間減半。逐步查找得到確定數(shù)據(jù)插入位置。

1.2 二分法數(shù)據(jù)快速查詢實(shí)施原理

在實(shí)際的查詢中，數(shù)據(jù)一般都是以對(duì)象的形式存儲(chǔ)，因此，需要先對(duì)數(shù)據(jù)進(jìn)行對(duì)象化，對(duì)此可采用OPC統(tǒng)一架構(gòu)模式，然后將數(shù)據(jù)分布式加載到對(duì)象服務(wù)器內(nèi)存中，以此實(shí)現(xiàn)數(shù)據(jù)的分布式存儲(chǔ)。再對(duì)數(shù)據(jù)對(duì)象實(shí)行本地查詢后對(duì)結(jié)果進(jìn)行排序，同時(shí)從中取得相應(yīng)的查詢結(jié)果，最后通過多級(jí)查詢?nèi)诤虾笠垣@取最終結(jié)果。在整個(gè)查詢過程中，查詢結(jié)果以數(shù)據(jù)塊為單位（數(shù)據(jù)記錄由實(shí)際查詢業(yè)務(wù)決定）經(jīng)過多級(jí)查詢?nèi)诤系茸罱K得到一個(gè)數(shù)據(jù)塊，將最后得到的數(shù)據(jù)塊反饋給用戶。詳細(xì)步驟如下：

在進(jìn)行本地查詢時(shí)，各對(duì)象服務(wù)器之間是并行執(zhí)行的。首先，本地查詢所需的基本數(shù)據(jù)塊的創(chuàng)建，是以每個(gè)對(duì)象服務(wù)器為基礎(chǔ)并在內(nèi)進(jìn)行創(chuàng)建，將本地?cái)?shù)據(jù)根據(jù)用戶查詢條件遍歷，滿足條件的元素按照序列添加到數(shù)據(jù)塊中。數(shù)據(jù)塊設(shè)置大小為K。添加時(shí)，二分法主要用于精準(zhǔn)地實(shí)施定位插入位置，然后再將數(shù)據(jù)插入數(shù)據(jù)塊中。如若數(shù)據(jù)塊的元素超過一定數(shù)量，則會(huì)產(chǎn)生溢出現(xiàn)象，此時(shí)應(yīng)將數(shù)據(jù)塊的首個(gè)元素后者末位元素移除。全部的有效元素插入之后，在得到本地查詢結(jié)果后開始進(jìn)入下一階段。

接下來的階段中，是參照數(shù)據(jù)對(duì)象之間的邏輯關(guān)系逐步合并對(duì)象服務(wù)器之間查詢結(jié)果的過程。針對(duì)每個(gè)級(jí)別，對(duì)象服務(wù)器依據(jù)收集下級(jí)對(duì)象服務(wù)器節(jié)點(diǎn)的查詢結(jié)果，創(chuàng)建一個(gè)新的數(shù)據(jù)塊定義并元素?cái)?shù)量為K，再通過二分法定位將所有查詢結(jié)果插入到數(shù)據(jù)塊中。在每次插入完成需要判斷數(shù)據(jù)塊是否溢出。如溢出，則需要移除首位元素或者末位元素。最后，將多級(jí)融合的數(shù)據(jù)塊發(fā)送給上級(jí)服務(wù)器。不斷循環(huán)執(zhí)行此過程，直到頂級(jí)對(duì)象服務(wù)器將融合后的查詢結(jié)果返回到平臺(tái)應(yīng)用中。

1.3 實(shí)驗(yàn)測(cè)試

借助于渭南市平臺(tái)與數(shù)據(jù)量，針對(duì)目前現(xiàn)有的海量數(shù)據(jù)實(shí)現(xiàn)二分法快速查詢與普通查詢算法進(jìn)行測(cè)試對(duì)比，進(jìn)行了如下實(shí)驗(yàn)：

（1） 測(cè)試數(shù)據(jù)量級(jí)從512 MB到1 TB逐步上升時(shí)兩種查詢方式的速度比較，如圖1所示?？梢钥闯鰯?shù)據(jù)量級(jí)越大，二分法查詢的速度越快。

圖1 數(shù)據(jù)量級(jí)對(duì)查詢速度的測(cè)試

（2） 測(cè)試數(shù)據(jù)量級(jí)為1 GB時(shí)數(shù)據(jù)返回結(jié)果條數(shù)與查詢時(shí)間的變化，如圖2所示?？梢钥闯龆址ㄔ跀?shù)據(jù)查詢結(jié)果上升時(shí)也優(yōu)于普通算法。

圖2 數(shù)據(jù)查詢目標(biāo)條數(shù)對(duì)查詢速度的測(cè)試

2 結(jié)語

針對(duì)當(dāng)前渭南智慧城市大數(shù)據(jù)基礎(chǔ)平臺(tái)的現(xiàn)狀，在此提出了一種基于面向?qū)ο蟛⑿杏?jì)算的海量數(shù)據(jù)快速查詢技術(shù)——二分法查詢，解決了平臺(tái)的目前遇到的問題。但是還需要在后期的維護(hù)升級(jí)中針對(duì)現(xiàn)狀進(jìn)行優(yōu)化，需要能在后期大數(shù)據(jù)技術(shù)的發(fā)展中尋求更好的解決方案。