複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/葉結點/9795627
複製
複製成功

葉結點

鎖定
索引的葉節點指構成B樹索引最底層的數據塊，其中存儲排序後的索引列值及此列值所在記錄的rowid，索引列值默認按升序排列。 [1] 
葉結點是離散數學當中的概念。一棵樹當中沒有子結點2（即度為0）的結點，稱為葉子結點，簡稱“葉子”。 葉子是指度為0的結點，又稱為終端結點。 [2] 
中文名
葉節點
外文名
Leaf Node
應用領域
網絡、程序、索引等 [3] 
別    名
葉子結點
類    別
信息技術、離散數學 [3] 
性    質
信息技術術語 [3] 

目錄

  1. 1 HBSTR－tree的葉節點
  2. 2 索引葉節點
  3. 3 ATM葉節點
  1. ▪ 介紹
  2. ▪ 創建步驟
  3. 4 IP葉節點
  4. ▪ 介紹
  5. ▪ 創建步驟
  1. 5 OSG葉節點（Geode）

葉結點HBSTR－tree的葉節點

圖1 HBSTR－tree的原理和框架示意圖 圖1 HBSTR－tree的原理和框架示意圖
採用集成 R 樹、哈希表和 B* 樹的混合索引方法HBSTR－tree，圖1是 HBSTR－tree的原理和框架示意圖。3種子索引結構的作用分別為：（1）R樹是主體索引結構，用於實現時空範圍查詢；（2）哈希表是輔助結構，維護移動對象的最新軌跡節點，用於成組插入採樣點；（3）B*樹是次要索引結構，軌跡節點的一維索引，用於實現目標對象的軌跡查詢。 [4] 
採樣點包含對象標識符、時間戳和空間位置等數據項，由於傳感器遮擋或者不穩定等因素，採樣點空間位置數據可能出現粗差，一般採用某些數據清洗方法過濾粗差數據。單個移動對象的採樣點數目數以萬計，分散管理採樣點不利於查找軌跡，對存儲利用率和創建效率均會產生負面影響。 [4] 
哈希表用於管理所有對象的最新軌跡節點，便於通過對象標識符查找對象的最新軌跡節點，當一個軌跡節點滿時，插入R樹，創建新的軌跡節點接收新採樣點。這樣，以節點形式成組插入時空R樹的方式，可大幅度提升索引創建效率。 [4] 
HBSTR－tree中，R樹是 N+1維（N 是空間維數，1指時間維）的時空R 樹，R樹節點最小包圍盒 MBR是其孩子集 合 的 時 空 坐 標 軸 最小范 圍，時間參考採用1970年以來的絕對秒數作為基準。上文軌跡節點作為R 樹的葉節點，採用一種新的節點插入算法將其索引項插入葉節點層的上一層中，利用節點選擇和節點分裂子算法優化時空R樹結構。時空R樹支持多種查詢類型，如搜索某時空範圍內的對象集合、對象軌跡，或者某時刻某空間範圍內的對象集合、對象位置，或者某時刻某空間點的最近鄰對象等。時空R樹搜索目標對象在某時間段內的軌跡並不高效。為解決該問題，採用軌跡節點的對象標識符 OID和起始時間tTimeStart組成一維關鍵碼（OID+tTimeStart）構建軌跡節點的 B* 樹索引，藉助B*樹的一維查詢能力，高效定位某對象在某時刻的軌跡節點，利用B*樹兄弟節點間的雙向指針進行軌跡追溯。軌跡節點通常包含近百個連續採樣點，相對於直接採樣點的一維索引結構，該方法節省存儲空間90%以上。 [4] 

葉結點索引葉節點

以在dept表的dname列上創建B樹索引為例，因dept表只有4行記錄，dname列上的索引只需要一個葉節點，即一個數據塊即可存儲全部索引數據，這個葉節點數據塊的內容是排序後的dname列值及相應列值所在記錄的rowid，這裏的rowid只包括文件號、數據塊號以及記錄在數據塊中的地址，並不包含dept表的偽列rowid中的object_id部分。 [1] 
圖2 B樹索引葉節點數據塊結構 圖2 B樹索引葉節點數據塊結構
索引在葉節點數據塊中的存儲格式與表的行數據存儲方式相似，每個由索引列值及row-id構成的組合可以看作一行記錄，這些行從數據塊的尾部開始填充，每行記錄在數據塊中的地址存儲在塊頭部的槽中。若在dept表的dname列上創建索引，則其只由一個葉節點構成，圖2給出B樹索引葉節點的結構。從圖2中可看出，B樹索引葉節點中的rowid部分由48個bit構成，前10個bit表示文件號，中間22個bit表示塊號，最後16個bit表示塊中的行號，即槽號。 [1] 

葉結點ATM葉節點

葉結點介紹

在多播組內創建一個葉節點相對簡單，在ATM網絡中，作為一個“葉節點”，必須隨時隨地監聽來自一個“根節點”的、要自己加入一個組的邀請。值得注意的是，在任何指定時刻，Windows 98和Windows 2000僅能支持一個ATM葉節點。換言之對任何ATM“點到多點”會話來説，在整個系統的範圍之內，只能有一個進程成為它的葉成員。 [3] 

葉結點創建步驟

在ATM網絡中，創建一個葉節點的步驟為： [3] 
（1）使用WSASocket函數，創建地址家族AF_ATM的一個套接字，同時設置WSA_FLAG_MULTIPOINT_C_LEAF和WSA_FLAG_MULTIPOINT_D_LEAF這兩個標誌。 [3] 
（2）使用bind函數，將套接字同本地ATM地址及端口綁定到一起。 [3] 
（3）調用listen（監聽）命令。 [3] 
（4）用accept或WSAAccept等候邀請。至於具體用哪個命令，要取決於使用的是哪種I/O（輸入/輸出）模型。建好連接後，葉節點便可開始接收來自根的數據，對ATM多播而言，數據流必須是單向的，由根節點至葉節點，不可逆反。 [3] 

葉結點IP葉節點

葉結點介紹

葉節點加入IP多播組的過程較簡單、因為每個節點都是一個“葉節點”，所以在加入一個組的時候採取的操作步驟都是一樣的。由於IP多播在Winsock1和Winsock2中都可以實現、所以可通過兩種API調用方法，來做成同樣的事情。值得注意的是，假如一個應用程序只是打算髮送數據，便不必加入一個IP多播組。向多播組發送數據時，網絡中傳輸的數據包與普通UDP包大致相同，只是目的地址換成了一個特殊的多播地址而已。但假如想接收多播數據，便必須加入一個組。但無論如何，除了對組成員資格的要求之外，IP多播通信與普通的UDP協議通信並無區別，因為兩者都是“無連接”的、“不可靠”的。 [3] 

葉結點創建步驟

在Winsock 1中，創建實現IP多播通信所需的葉節點的基本步驟： [3] 
（1）使用socket函數創建一個套接字，注意要設為AF_INET地址家族以及SOCK_DGRAM套接字類型。要想初始化一個多播套接字，不必設置任何特殊標誌，因為socket函數本身便沒有提供標誌參數。 [3] 
（2）如果想從組內接收數據，需要將套接字同一個本地端口綁定到一起。 [3] 
（3）調用setsockopt函數，同時設置 IP ADD MEMBERSHIP選項，指定想加入的那個組的地址結構。 [3] 
如果使用的是Winsock 2，那麼步驟（1）和（2）是相同的，而步驟（3）要換成調用WSAJoinLeaf函數，將葉節點加入那個組。 [3] 

葉結點OSG葉節點（Geode）

Geode類（即Geometry Node）相當於OSG中的葉節點。它沒有子節點，但是包含了osg::Drawable對象，而osg::Drawable對象中存放了將要被渲染的幾何體，一般的可繪製幾何體都是通過Geode節點來傳向root節點進行渲染。Geode節點是OSG幾何繪製的最高管理節點。 [5] 
參考資料