[發明專利]基于平衡二叉樹的快速查缺方法

在審

• 申請號: 202110192467.0
• 申請日: 2021-02-20
• 公開（公告）號: CN112860634A
• 公開（公告）日: 2021-05-28
• 發明（設計）人: 吳仕富
• 申請（專利權）人: 杭州卯方科技有限公司
• 主分類號: G06F16/14
• 分類號: G06F16/14;G06F16/901
• 代理公司: 浙江新篇律師事務所 33371
• 代理人: 張冬堯

本發明公開了基于平衡二叉樹的快速查缺方法，包括如下步驟：S1、構建一個64位的整形數組Array，每個比特位表示一個分片，比如有512個分片，數組的第一個64位可以表示編號為0～63的分片，數組的第二個64位可以表示編號為64～127的分片，以此類推；S2、當收到一個分片后，通過計算分片在數組中的位置，并設置相應比特位為1；S3、通過平衡二叉樹規則，將所有葉子節點兩兩做與運算，并構建其父節點，直至構建出根節點。本發明的有益效果是：通過平衡二叉樹，以及比特位分塊的快速缺失查詢，在(N文件或消息分片的數量，M是缺失文件或分片的數量)復雜度的性能下，快速找到哪些分片是缺失的。

技術領域

本發明涉及網絡數據技術領域，具體為基于平衡二叉樹的快速查缺方法。

背景技術

在大型網絡數據傳輸場景中，接收端都需要檢查收到的數據是否完整，而發送數據一般都會采用分片和并發送的方式，這就會導致接收端收到的數據，并不是連續和完整的，這個時候接收端就需要去遍歷檢查每一個分片是否到達，對于大數據和分布式文件系統，這種遍歷所帶來的的性能損耗是比較大的，現有的數據缺失查詢，一般都采用遍歷的方式，如果有N個分片，其效率是O(N)，為此，我們提出基于平衡二叉樹的快速查缺方法。

發明內容

本發明的目的在于提供基于平衡二叉樹的快速查缺方法，以解決上述背景技術中提出的問題。

為實現上述目的，本發明提供如下技術方案：基于平衡二叉樹的快速查缺方法，包括如下步驟：

S1、構建一個64位的整形數組Array，每個比特位表示一個分片，比如有512個分片，數組的第一個64位可以表示編號為0～63的分片，數組的第二個64位可以表示編號為64～127的分片，以此類推；

S2、當收到一個分片后，通過計算分片在數組中的位置，并設置相應比特位為1；

S3、通過平衡二叉樹規則，將所有葉子節點兩兩做與運算，并構建其父節點，直至構建出根節點；

S4、構建出根節點后，即可從根節點開始，向下查詢出哪些葉子節點是有缺失的。

優選的，所述步驟S1中每個節點只顯示了64位的最后8位，前面56位都是默認1。

優選的，所述步驟S4中其查詢過程為：如果根節點為Uint64full(64位整數每一個比特位都是1)，則表示所有分片都已經收到，數據完整，查詢效率為0(1)，否則查詢左子樹是否為Uint64full，然后查詢右子樹，通過查詢四個過程(查詢1、查詢2、查詢3和查詢4)即可快速查詢到葉子結點3是有缺失的，因為每個節點是64位表示，所以雖然確定葉節點3有缺失，但是還不確定是哪一個比特位是0，為了不遍歷64次，將再次對這個查詢進行優化。

與現有技術相比，本發明的有益效果是：通過平衡二叉樹，以及比特位分塊的快速缺失查詢，在(N文件或消息分片的數量，M是缺失文件或分片的數量)復雜度的性能下，快速找到哪些分片是缺失的。

附圖說明

此處所說明的附圖用來提供對本申請的進一步理解，構成本申請的一部分，本申請的示意性實施例及其說明用于解釋本申請，并不構成對本申請的不當限定。在附圖中：

圖1為本發明平衡二叉樹的查缺流程圖。

具體實施方式

下面對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基于本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬于本發明保護的范圍。

請參閱圖1，本發明的基于平衡二叉樹的快速查缺方法，包括如下步驟：