[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

TWI549009B - 資料庫管理方法、資料庫管理系統，以及資料庫樹狀結構 - Google Patents

資料庫管理方法、資料庫管理系統，以及資料庫樹狀結構 Download PDF

Info

Publication number
TWI549009B
TWI549009B TW103135611A TW103135611A TWI549009B TW I549009 B TWI549009 B TW I549009B TW 103135611 A TW103135611 A TW 103135611A TW 103135611 A TW103135611 A TW 103135611A TW I549009 B TWI549009 B TW I549009B
Authority
TW
Taiwan
Prior art keywords
page
record
ufk
lfk
key
Prior art date
Application number
TW103135611A
Other languages
English (en)
Other versions
TW201514734A (zh
Inventor
徐敬植
金甲榮
李基烈
Original Assignee
納寶股份有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 納寶股份有限公司 filed Critical 納寶股份有限公司
Publication of TW201514734A publication Critical patent/TW201514734A/zh
Application granted granted Critical
Publication of TWI549009B publication Critical patent/TWI549009B/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2228—Indexing structures
    • G06F16/2246—Trees, e.g. B+trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/40—Information retrieval; Database structures therefor; File system structures therefor of multimedia data, e.g. slideshows comprising image and additional audio data
    • G06F16/43—Querying
    • G06F16/438—Presentation of query results
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/24—Querying
    • G06F16/245—Query processing
    • G06F16/2455—Query execution
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/30—Information retrieval; Database structures therefor; File system structures therefor of unstructured textual data
    • G06F16/31—Indexing; Data structures therefor; Storage structures
    • G06F16/316—Indexing structures

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Data Mining & Analysis (AREA)
  • Databases & Information Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Computational Linguistics (AREA)
  • Multimedia (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Description

資料庫管理方法、資料庫管理系統，以及資料庫樹狀結構
本發明的一或更多個實施例係與一種資料庫(DB)管理方法、DB管理系統，以及DB樹狀結構相關，以及更特別地，係與使用一索引壓縮方法的一種DB管理方法、DB管理系統，以及DB樹狀結構相關。
本發明係以2013年10月15日提出的韓國專利申請案第10-2013-0122951號主張優先權，在此並完整引用作為參考。
資料庫管理系統(database management system,DBMS)是用於管理資料庫的系統，資料庫儲存大量的資料，是目前資訊不斷大量產出的時代中重要且必要的一種元件。
DBMS將資料以表(table)的形式儲存於資料庫中。在此，表是資料庫中儲存資料的基本結構，而一個表包括至少一個記錄(record)。記錄代表的是表的一行。同樣地，每一記錄包括至少一欄(column)，其中欄代表在一具有實際的表項目名稱之領域，也可稱為一屬性(attribute)或一欄位(field)。
當一外部來源輸入一特定的查詢時，DBMS根據輸入的特定查詢(query)，針對資料庫執行像是選擇、插入、更新，以及刪除資料等。在此，查詢是關於儲存在資料庫的表內的資料的需求描述，也就是要對資料執行的動作，它是以一語言，像是結構化查詢語言(structured query language,SQL)表示。
由於資料量大，DBMS一般會包括一索引(index)。在此，索引是能夠增進資料庫欄位的表的搜尋速度之資料結構，而索引內的資料是{金鑰值(key value)，指標(pointer)}對的結構，所以能夠很快地存取資料記錄(元組(tuple))。
在先前技術此一段落內所揭露是本發明的發明人已經熟悉，或者是在達成本發明的過程中所得到的技術資訊。因此，在此可能會包含並非一般大眾所熟悉的前案資訊。
本發明的一或更多個實施例提供一種資料庫(DB)管理方法、DB管理系統，以及DB樹狀結構，其中在形成DB的一索引時，一個頁面內包括的複數個記錄的金鑰值之一下限值與一上限值係被儲存為分離符(separator)，而該些分離符係被用來刪除該些金鑰值的一重複部分以節省一儲存該索引的頁面之儲存空間，並因此而提升該DB的效能。
本發明的一或更多個實施例提供一種資料庫(DB)管理方法、DB管理系統，以及DB樹狀結構，其中在執行時間(run-time)內可設定壓縮，在特定區域的插入/刪除運算的負荷高時不執行壓縮，因此可提升DB的操作效能。
本發明的一或更多個實施例提供一種資料庫(DB)管理方法、DB管理系統，以及DB樹狀結構，其中本發明不需要額外記錄有關二次壓縮方法與範圍的元資料，因此，與一般方法相較下，可提升壓縮效率，其中當儲存在頁面內的記錄數目增加時，元資訊會被壓縮納入記錄中。
本發明的一或更多個實施例提供一種資料庫(DB)管理方法、DB管理系統，以及DB樹狀結構，其中無論何時要檢視索引的樹狀結構，可使用每一頁面的下籬金鑰(lower fence key,LFK)與上籬金鑰(upper fence key,UFK)來對一葉節點執行有效性檢查(validity check)，就可很簡單地決定索引結構的錯誤。
在以下的說明中將會提出本發明的額外型態，其中有些已清楚描述，或者在實施本發明的實施例後也可了解。
根據本發明的一或更多個實施例，一種資料庫(DB)管理方法包含：由一索引管理器儲存在每一頁面包括的複數個記錄的金鑰值的一下限值作為一下籬金鑰(lower fence key,LFK)，或複數個記錄的金鑰值的一上限值作為一上籬金鑰(upper fence key,UFK)；萃取來自每一頁面包括的複數個記錄的金鑰值的一共同區域，作為一前置(prefix)；以及由該索引管理器儲存從該複數個記錄的金鑰值去除對應該前置的一部分所取得的一剩餘部份。
前置可儲存在該LFK或該UFK內。
從該複數個記錄的原始金鑰值去除該前置所取得的金鑰值係儲存在記錄中，除了儲存該LFK或該UFK的地方之外。
該複數個記錄的每一個係為一包含複數個金鑰值的多欄之形式。
在該複數個金鑰值中的一金鑰值的一部份於形成一個頁面的記錄中均具有一相同數值，該金鑰值的一部分可被萃取為該前置。
每一個頁面可為一具有一B樹狀或B+樹狀結構之葉節點。
該DB管理方法更包含由該索引管理器回復該些頁面的每一個頁面包括的該複數個記錄之原始金鑰值，其中該回復步驟包含：決定該LFK與該UFK是否存在於一頁面內；如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該LFK與該UFK共同的一前置；以及藉由結合該被萃取的前置與一相關記錄的金鑰值回復原始金鑰值。
如果該LFK與該UFK並不存在於該頁面內，則儲存在每一記錄內的金鑰值可為原始金鑰值。
該DB管理方法更包含由該索引管理器增加一新記錄至該些頁面的每一個頁面，或由該索引管理器更改一預存記錄，其中該增加或更改步驟包含：決定該LFK與該UFK是否存在於一頁面內；如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該LFK與該UFK共同的一前置；以及將一要增加的記錄去除該前置所取得的剩餘金鑰值增加至該頁面的一記錄，或將該頁面的該記錄更改為從一記錄去除該前置所取得的剩餘金鑰值以更換該頁面的該記錄。
如果該LFK與該UFK並不存在於該頁面內，則不萃取該前置，以及可將一新記錄增加至一頁面或更改該頁面的一預存記錄。
根據本發明的一或更多個實施例，一種資料庫(DB)管理方法包含：產生一具有一B樹狀或B+樹狀結構的索引；回復在該索引內的一預定記錄；以及增加一記錄至該索引或更改在該索引內的該預定記錄，其中該DB具有一B樹狀或B+樹狀結構，而該索引的產生步驟包括在至少一個葉節點的至少一端儲存在該至少一個葉節點內的金鑰值的一下限值作為一下籬金鑰(LFK)，或儲存在該至少一個葉節點內的金鑰值的一上限值作為一上籬金鑰(UFK)。
根據本發明的一或更多個實施例，一種資料庫(DB)管理系統包含：一接收與分析一查詢的查詢分析器，其中該查詢分析器係定義一用於被包括在一特定表內的記錄之取回要求與一用於至少一個被包括在該記錄內的欄之更新要求；一執行計畫產生器，其產生一用於執行該被分析的查詢之執行計畫；一執行計畫執行單元，其根據該執行計畫取回該記錄與更新該至少一個欄以執行該執行計畫；以及一索引管理器，其包含一索引產生器，其產生一關於該特定表的索引，並儲存在該索引的每一頁面包括的複數個記錄的金鑰值之一下限值作為一下籬金鑰(LFK)，或複數個記錄的金鑰值的一上限值作為一上籬金鑰(UFK)。
索引產生器萃取來自每一頁面包括的複數個記錄的金鑰值的一共同區域，作為一前置。
索引產生器可儲存從該複數個記錄的金鑰值去除對應該前置的一部分所取得的一剩餘部份，該前置為每一頁面包括的複數個記錄的金鑰值的共同區域。
前置僅被儲存在該LFK或該UFK內。
從該複數個記錄的原始金鑰值去除該前置所取得的金鑰值係被儲存在記錄中，除了儲存該LFK或該UFK的地方之外。
索引管理器更包含一記錄回復器，其回復來自該索引的每一頁面包括的複數個記錄之原始金鑰值。
記錄回復器可決定該LFK與該UFK是否存在於一頁面內； 如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該前置；以及藉由結合該被萃取的前置與該頁面的一相關記錄的金鑰值以回復原始金鑰值。
索引管理器更包含一記錄更新器，其增加一新記錄至該索引的該些頁面的每一個頁面，或更改一預存記錄。
記錄更新器決定該LFK與該UFK是否存在於一頁面內；如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該前置；以及將一要增加的記錄去除該前置所取得的剩餘金鑰值增加至該頁面的一記錄，或將該頁面的該記錄更改為從一記錄去除該前置所取得的剩餘金鑰值以更換該頁面的該記錄。
根據本發明的一或更多個實施例，一種具有一B樹狀或B+樹狀結構的資料庫(DB)樹狀結構包含：一位於該B樹狀或B+樹狀結構的一最頂層之根節點，其儲存至少一個分離金鑰值，以及至少一個葉節點，其在至少一個葉節點的至少一端儲存在該至少一個葉節點內的金鑰值的一下限值作為一下籬金鑰(LFK)，或儲存在該至少一個葉節點內的金鑰值的一上限值作為一上籬金鑰(UFK)。
存在於該至少一個葉節點內介於該LFK與該UFK之間的一記錄可僅儲存從該記錄的金鑰值去除一共同區域所取得的剩餘金鑰值。
儲存在該根節點內的該至少一個分離金鑰值可為一鄰近的葉節點的LFK或另一鄰近葉節點的UFK。
該至少一個葉節點的最左邊葉節點不能儲存LFK，而該至少一個葉節點的最右邊葉節點不能儲存UFK。
100‧‧‧資料庫(DB)管理系統
110‧‧‧資料庫(DB)
120‧‧‧查詢分析器
130‧‧‧執行計畫產生器
140‧‧‧執行計畫執行單元
150‧‧‧分項管理器
160‧‧‧索引管理器
161‧‧‧索引產生器
163‧‧‧記錄回復器
165‧‧‧記錄更新器
170‧‧‧記憶體
S100、S110、S120、S130‧‧‧步驟
S200、S210、S220、S230、S240‧‧‧步驟
S300、S310、S320、S330、S340‧‧‧步驟
透過以下的實施例說明，並配合所附圖表，將可清楚了解本發明，其中：圖1為根據本發明的實施例之資料管理系統的概要方塊圖；圖2A為根據本發明的實施例之資料管理方法在產生一索引時的流程圖； 圖2B為根據本發明的實施例之資料管理方法在回復一記錄時的流程圖；圖2C為根據本發明的實施例之資料管理方法在增加/更改記錄時的流程圖；圖3為根據本發明的實施例之應用DB管理方法與系統的B樹狀索引的結構圖；圖4為一通用B樹狀頁面的金鑰值之配置圖；圖5為根據本發明的實施例，一根據DB管理方法與系統的B樹狀頁面的金鑰值之配置圖；以及圖6(a)與(b)所示為根據本發明的實施例之應用DB管理方法與系統以分割一B樹狀索引內的頁面之流程。
以下將參考實施例並配合圖表以說明本發明，其中類似的參考標號係用以標示類似的元件。由此看來，在此所述的實施例可能會具有不同形式，同時不應限制於在此提出的說明。因此，實施例僅用以配合圖表以解釋本說明書的各種型態。
接下來將配合附屬圖表以詳細說明一或更多個實施例，俾使熟悉此技藝者能夠實施本發明。
圖1為根據本發明的實施例之資料庫(DB)管理系統100的概要方塊圖。參考圖1，根據本發明的實施例之DB管理系統係如下設置。
首先，各種型態的資料係以表(table)的形式儲存在DB 110內，如上述，每一表包括至少一個記錄(record)，而每一記錄包括至少一個欄(column)。舉例來說，當DB儲存佈告(bulletin)在預定的佈告版上，一個表代表一群佈告，一個記錄代表一個佈告，而欄代表的是儲存佈告識別符、佈告撰寫者、或者佈告點擊次數。圖1包括了複數個DB 110，但是本發明的實施例不在此限，DB 110的數目與結構可根據DB管理系統100的結構、儲存的資料量，以及DB管理系統100的目的而改變。
DB管理系統100連接DB 110以便系統性地管理DB 110， 像是更新或刪除DB 110記錄的資料，大致上並包括查詢分析器(query analyzer)120、執行計畫產生器(execution plan generator)130，以及一執行計畫執行單元(execution plan execution unit)140。另外，DB管理系統100更可包括一分項管理器(entry manager)150與索引管理器(index manager)160。
查詢分析器120從任何一個與DB管理系統100互動的外部伺服器(未顯示)或管理者終端(未顯示)接收用於處理DB 110的資料之查詢，並分析所收到的查詢。查詢分析器120可包括查詢接收器與剖析器，也可進一步包括一有效性驗證器。
執行計畫產生器130根據查詢分析器120的有效性驗證器決定為有效的剖析樹，產生一執行計畫，用於取回要求的記錄與更新在要求的記錄中的欄，並儲存所產生的執行計畫於記憶體170內，以下將會說明。在此，執行計畫代表一資料結構，其中包括從一特定表取回記錄的方法、結果記錄清單，以及是否要對需更新的欄執行增加運算的資訊。
根據一實施例，執行計畫產生器可選擇順序掃描方法(sequential scanning method)和索引掃描方法(index scanning method)其中任一種以從特定表取回一要求的記錄。在此，順序掃描方法依序地掃描在特定表中的記錄，取回具有一要求的記錄的識別符之記錄，而索引掃描方法僅掃描相關的索引以取回要求的記錄，這是因為索引是根據記錄的識別符所產生。DB管理系統100的索引將會在以下說明。
執行計畫執行單元140根據執行計畫產生器130所產生的執行計畫從特定表取回要求的記錄，並藉由對要被更新的欄的實體位置所對應的記錄上的欄數值，執行一增加運算，以更新欄數值。詳細地說，執行計畫執行單元140產生一交易，用於在交易過程中處理由執行計畫產生器130所產生的執行計畫。在此，交易所指為一個邏輯工作單元，可由至少一個結構化查詢語言(structured query language,SQL)的敘述來定義。藉由這類交易，可以確保資料一致性與同時性。
DB管理系統100更可包括分項管理器150，用於產生或刪除一包括記錄的識別符與要被更新的欄之識別符，並藉由將產生的分項與包括在一分項內的欄識別符之欄數值配對，將產生的分項儲存於記憶體170 內，其中要被更新的欄之欄數值可與分項管理器150所產生的分項配對，並被儲存在記憶體170內。
同時，DB管理系統100更可包括索引管理器160，其產生或刪除一索引，並將產生的索引儲存在記憶體170內。索引管理器160更可包括一索引產生器161、記錄回復器163，以及記錄更新器165。
索引產生器161產生一關於DB 110的索引，此時，在索引的每一頁面的金鑰值之下限值可被儲存為下籬金鑰(lower fence key,LFK)，而金鑰值之上限值可被儲存為上籬金鑰(UFK)。另外，索引產生器161萃取形成每一頁面的複數個記錄之金鑰值的共同區域為一前置(prefix)。接著，索引產生器161將每一頁包括的複數個記錄之金鑰值中，對應前置的部份刪除，然後儲存該些金鑰值於索引內。
記錄回復器163回復索引的每一頁的記錄之原始金鑰值。詳細地說，記錄回復器163決定LFK與UFK是否存在於每一頁面，如果有LFK與UFK的話，藉由比較LFK與UFK以萃取前置，並結合萃取的前置與記錄的金鑰值以回復原始金鑰值。
記錄更新器165增加一新的記錄至索引的每一頁面，或更改一預存記錄(pre-existing record)。詳細地說，記錄更新器165決定LFK與UFK是否存在於每一頁面，以及如果LFK與UFK存在，則比較LFK與UFK以萃取前置，將一要增加的記錄去除該前置所取得的剩餘金鑰值增加至頁面的一記錄，或將該頁面的記錄更改為從一記錄去除該前置所取得的剩餘金鑰值以更換頁面的記錄。
以下將參考圖2詳細說明索引產生器161產生索引，記錄回復器163回復記錄，以及記錄更新器165更新記錄的方式。
在此將詳細說明使用分離符為基(separator-based)的索引壓縮方法之DB管理方法。
圖2A至圖2C是根據本發明的一實施例之DB管理方法流程圖；圖3為根據本發明的實施例之應用DB管理方法與系統的B樹狀索引的結構圖；圖4為一通用B樹狀頁面的金鑰值之配置圖；以及圖5為根據本發明的實施例，一根據DB管理方法與系統的B樹狀頁面的金鑰值之 配置圖。
參考圖2A至5，根據本發明的DB管理方法包括產生一索引(步驟S100)、回復索引的記錄(步驟S200)，以及增加或更改索引的記錄(步驟S300)。
以下將詳細說明DB管理方法。
索引指示資料結構，因此可加快對DB欄位中的表之運算速度。索引可利用在表中的一個欄(單一欄索引)或多個欄(多欄索引)產生，在存取記錄時不僅可提供高速搜尋運算，同時也是有效率的排序運算之基礎。儲存索引所需的磁碟空間通常要比儲存表的空間來得小，這是因為索引通常具有金鑰和欄位，而不具有表的其他細部項目。
B樹(或B+樹)是DB和檔案系統中廣泛用來形成索引之樹狀資料結構，其為關聯性映射資料結構，用以快速地查詢具有特定金鑰值的記錄。由於存取高容量磁碟中的資料之速度慢，B樹(或B+樹)提供頁面的樹狀結構以降低輸出入(I/O)的次數。實際記錄的金鑰值和位置(物件識別符(object identifier)或記錄識別符)係被記錄在一個頁面中，其中金鑰值係被當作屬性來排序。換句話說，索引記錄(在此也可直稱為記錄)是藉由結合金鑰值一物件識別符{key-OID}而形成。
基於此特性，在一個頁面內的記錄之臨近金鑰值可能會相當類似。舉例來說，如果以識別(ID)號碼、郵件資料夾號碼，以及郵件序號作為公司郵件系統的索引金鑰(也就是個多欄索引)，而某一員工總共有100,000封郵件，10,000封郵件在一個郵件資料夾，這10,000封郵件具有相同的ID號碼與相同的郵件夾號碼，而100,000封郵件在一索引內的ID號碼相同。如果根據一般方法，將1,000封郵件記錄在一通用B樹的一個頁面內，那有10個頁面會重複地儲存相同的ID號碼與相同的郵件夾號碼。因此，由於重複儲存相同的數值，記憶體就被浪費了。
因此，根據本發明的一或更多個實施例的使用分離符為基的索引壓縮方法之DB管理方法可藉由將一個頁面的金鑰值中重複儲存的前置存放在下籬金鑰(LFK)與上籬金鑰等分離符中，因此而節省記憶體空間。
回到圖2A，根據本發明的一實施例，DB管理方法產生索 引(步驟S100)的步驟包括在一個頁面內儲存金鑰值的下限值作為LFK，或儲存金鑰值的上限值作為UFK(步驟S110)，萃取形成該頁面的複數個記錄的金鑰值之一共同區域作為一前置(步驟S120)，並且從金鑰值刪除前置，然後儲存金鑰值(步驟S130)。
以下將詳細說明步驟S100。
參考圖3，其中所示為在一索引中用來快速搜尋DB內的記錄資料之B樹狀索引的結構，根據本發明的實施例，B樹狀索引包括指示實際記錄資料，以及上中間節點(upper intermediate node)之葉節點(leaf node)。根節點是上中間節點之中的最頂端節點。在圖3，有4個葉節點與一個中間節點，而該中間節點為根節點。每一個葉節點形成一個頁面。換句話說，在圖3中4個葉節點形成4個頁面。
在此，圖3的B樹狀索引的根節點具有第一到第三分離金鑰值(separation key value)P1、P2，與P3。第一分離金鑰值P1是分離第一頁面與第二頁面的分離符(separator)，第二分離金鑰值P2是分離第二與第三頁面的分離符，而第三分離金鑰值P3是分離第三與第四頁面的分離符。
如上述，根據本發明的實施例，DB管理方法在每一頁面內儲存金鑰值的一下限值作為LFK，以及金鑰值的一上限值作為UFK。在圖3中，LFK被儲存在每一頁面的左端以定義每一頁面的下限值，而UFK被儲存在每一頁面的右端以定義每一頁面的上限值。
同樣地，根據本發明的實施例，DB管理方法萃取該頁面中介於LFK與UFK之間的複數個記錄的金鑰值之一共同區域作為一前置，從複數個記錄的金鑰值刪除前置，除了LFK與UFK之外，並且儲存剩餘的金鑰值，藉此避免儲存重複的資料以節省記憶體空間。
換句話說，第一分離金鑰值P1是第一頁面的UFK(UFK1)，同時是第二頁面的LFK(LFK2)。同樣地，第二分離金鑰值P2是第二頁面的UFK(UFK2)，同時也是第三頁面的LFK(LFK3)。同樣地，第三分離金鑰值P3是第三頁面的UFK(UKF3)，同時是第四頁面的LFK(LFK4)。在此，4個葉節點的最左邊的葉節點(第一頁面)不能設定LFK，所以不會從第一頁面萃取前置。同樣地，4個葉節點的最右邊的葉節 點(第四頁面)不能設定UFK，所以不會從第四頁面萃取前置。
為了進一步的說明，圖4所示為一通用B樹狀頁面的金鑰值之配置；圖5為根據本發明的實施例，一根據DB管理方法與系統的B樹狀頁面的金鑰值之配置，二圖用來互相比較。為了方便說明，這裡假定只有10個記錄。
參考圖4，ID號碼(KR10000)與郵件夾號碼(FD0001)被重複儲存在一個頁面的10筆記錄內。另一方面，參考圖5，根據本發明的實施例之DB管理方法，在一頁面中的金鑰值的共同部分是ID號碼(KR10000)與郵件夾號碼(FD0001)，這部分只有儲存在定義頁面的下限值之LFK與定義頁面的上限值之UFK內，而刪除前置後的金鑰值被儲存在除了LFK與UFK以外的記錄中。換句話說，在10筆記錄中相同的金鑰值ID號碼(KR10000)與郵件夾號碼(FD0001)會被刪除，只有不同的金鑰值，也就是郵件序號，會被儲存在圖5的每一記錄內。
以下將詳細說明根據本發明的實施例之DB管理方法如何回復記錄。參考圖2B與圖5，回復記錄(步驟S200)包括決定LFK與UFK是否存在於一頁面內(步驟S210)；如果LFK與UFK存在於該頁面內，比較LFK與UFK以萃取LFK與UFK共同的一前置(步驟S220)；以及藉由結合該被萃取的前置與一相關記錄的金鑰值回復原始金鑰值(步驟S230)。以下將詳細說明步驟S200。
首先，經由一二元搜尋(binary search)找到要回復金鑰值的頁面，並決定LFK與UFK是否存在於頁面內。如果LFK與UFK的任一個都不存在於頁面內，則該頁面沒有被壓縮，也就是說，重複的資料沒有用前置刪除，並決定儲存在頁面的每一記錄的金鑰值均為原始金鑰值(步驟S240)。同時，如果LFK與UFK均存在於頁面內，則決定資料已經有用頁面內的前置壓縮過，因此會執行一預定的回復常式(predetermined restoration routine)。換句話說，比較頁面的下限值LFK與上限值UFK以萃取LFK與UFK的一共同區域，也就是前置。在圖5，LFK與UFK的共同區域KR10000：FD0001可萃取為前置。接著，原始金鑰值可藉由結合萃取的前置與頁面的每一記錄的金鑰值而回復。換句話說，SN10001經回復後的原始 金鑰值為KR10000：FD0001：SN10001。
以下將說明根據本發明的實施例之DB管理方法如何增加或更新一記錄。參考圖2C與5，增加或更改記錄(步驟S300)包括決定LFK與UFK是否存在於一頁面內(步驟S310)；如果LFK與UFK存在於頁面內，比較LFK與UFK以萃取一前置(步驟S320)；以及將一要增加的記錄去除該前置所取得的剩餘金鑰值增加至頁面的一記錄，或將該頁面的記錄更改為從一記錄去除前置所取得的剩餘金鑰值以更換該頁面的記錄(步驟S330)。以下將詳細說明步驟S300。
首先，經由二元搜尋找到要增加或更改的頁面，並決定LFK與UFK是否存在於頁面內。如果LFK與UFK的任一個都不存在於頁面內，則該頁面沒有被壓縮，也就是說，重複的資料沒有用前置刪除，因此新的金鑰值會被增加至相關記錄的金鑰值，或相關記錄的金鑰值在沒有任何分離程序的情形下更改(步驟S340)。同時，如果LFK與UFK均存在於頁面內，則決定資料已經有用頁面內的前置壓縮過，因此會執行一預定的拆解常式(disassembling routine)。換句話說，比較頁面的下限值LFK與上限值UFK以萃取LFK與UFK的一共同區域，也就是前置。在圖5，LFK與UFK的共同區域KR10000：FD0001可萃取為前置。接著，將一要增加的記錄去除該前置所取得的剩餘金鑰值增加至頁面的金鑰值，或將該頁面的記錄更改為從一記錄去除前置所取得的剩餘金鑰值以更換該頁面的金鑰值。舉例來說，當要增加的金鑰值為KR10000：FD0001：SN13000，前置為KR10000：FD0001，因此只有去除前置後的金鑰值SN13000會被增加至一頁面。
以下將說明根據本發明的實施例之DB管理方法如何分割一頁面或合併頁面。
圖6(a)與(b)所示為根據本發明的實施例之應用DB管理方法與系統以分割一B樹狀索引內的頁面之流程。
圖6(a)的B樹狀索引的根節點首先具有2個分離金鑰值，也就是第一與第二分離金鑰值P1與P2。第一分離金鑰值P1為用於分離第一頁面與第二頁面之分離符，而第二分離金鑰值P2為用於分離第二頁面與第 三頁面之分離符。同樣地，第一分離金鑰值P1為第一頁面的UFK(UFK1)，同時也是第二頁面之LFK(LKF2)。同樣地，第二分離金鑰值P2為第二頁面的UFK(UFK2)，同時也是第三頁面的LFK(LFK3)。
在此，讓我們假定第二頁面沒有多餘的儲存空間，因此需要根據第一與第二分離金鑰值P1與P2之間的預定值S來分割第二頁面。
在此情形下，如圖6(b)所示，第二頁面儲存預定值S，以回復作為新的UFK(UFK2)。接著，使用預先存在的LFK(LKF2)和新產生的UFK(UFK2)再次壓縮資料。換句話說，藉由比較LFK(LFK2)與UFK(UFK2)以萃取前置，並僅儲存從記錄的金鑰值中，除了LFK(LKF2)與UFK(UFK2)之外，刪除前置後得到的剩餘金鑰值。
同時，在圖6(b)中新產生的第三頁面儲存預定值S作為LFK(LFK3)。接著，儲存圖6(a)的第二頁面的UFK(UFK2)作為第三頁面的UFK(UFK3)。接著，使用圖6(b)中的LFK(LKF3)與UFK(UFK3)再次壓縮資料。換句話說，藉由比較LFK(LFK3)與UFK(UFK3)以萃取前置，並僅儲存從記錄的金鑰值中，除了LFK(LKF3)與UFK(UFK3)之外，刪除前置後得到的剩餘金鑰值。
最後，於圖6(b)的第三頁面，在母節點(在此為根節點)的第一與第二分離金鑰值P1與P2之間，插入預定值S作為新的分離金鑰值。
同時，儘管沒有在圖6中表示，如果頁面沒有壓縮，也就是沒有用前置刪除重複資料，而且根據新的分離金鑰值S分割了頁面，則新的分離金鑰值S會被設為原有頁面的UFK，然後可以使用新產生的UFK和預先存在的LFK壓縮資料。同時，在分割原始頁面所產生的新頁面中，新的分離金鑰值S會被設為LFK，但是因為沒有設定UFK，所以新頁面內的資料不會被壓縮。
同樣地，儘管沒有在圖6中表示，如果2個鄰近頁面可以合併，也就是如果儲存在2個鄰近頁面內的資料數目的總和小魚或等於可儲存在一個頁面內的記錄的最大數目，則這2個鄰近頁面可被合併。在此，如果2個鄰近頁面均為已壓縮頁面，也就是如果已經用前置刪除重複資料， 則合併2個鄰近頁面後的資料有被壓縮。另一方面，如果2個鄰近頁面中只要有一個頁面沒有壓縮，就不會發生合併動作。表1是比較一般DB管理方法與系統的索引的總頁數和根據本發明的一或更多個實施例的DB管理方法與系統後所得出的結果。同樣地，表2是比較一般DB管理方法與系統的平均金鑰長度(average key length)，以及根據本發明的一或更多個實施例的DB管理方法與系統的平均金鑰長度後所得出的結果。
如表1與2所示，在應用根據本發明的一或更多個實施例之DB管理方法與系統時，與一般DB管理方法與系統相較下，總頁數減少19%，而平均金鑰長度減少31%。換句話說，根據本發明的一或更多個實施例可節省儲存空間，因此可提升DB的效能。
在根據本發明的實施例之DB管理方法中，作為B樹狀頁面的分離符之金鑰值會被設定為一虛擬金鑰-物件識別符{virtual key-OID}，並被加至B樹狀頁面2端的每一個籬金鑰(LFK與UFK)，因此可快速地執行根據LFK與UFK取得原始金鑰值的合併程序以及刪除前置的拆解程序。
如果LFK或UFK並沒有存在於頁面內，則可用一般方法儲存記錄，所以索引可能會包括一個壓縮頁面(每一記錄的前置均已刪除)以及一未壓縮頁面(每一記錄的前置都沒有被刪除)。同樣地，在一具有LFK與UFK的頁面中可能會有壓縮資料與未壓縮資料共存。因此，在執行時間內可動態設定壓縮，不論B樹的目前狀態為何。因此，在特定區域的插入 /刪除運算的負荷增加時不執行壓縮，因此可提升DB的運算效能。
同時，由於使用LKF與UFK來決定前置，不需要額外記錄有關二次壓縮方法與範圍的元資料，因此，當儲存在頁面內的記錄數目增加時，比較一般方法將元資訊納入壓縮記錄中，本發明可提升壓縮效率。
根據本發明的實施例，由於只儲存沒有前置的金鑰值，所以在B樹的一個頁面中可以儲存更多記錄。因為可節省儲存空間，所以儲存空間可被放在主記憶體的緩衝器快取內，藉此提升DB的效能。此外，與一般壓縮方法相較，根據本發明的實施例的DB管理方法，可輕易的執行分割頁面與回復記錄，由於儲存結構沒有改變，相容性較低也沒有關係，而索引的結構也很簡單，其中只要增加一指示LFK與UFK的旗標，而不用額外記錄其他元資料。
另外，根據本發明的實施例之DB管理方法，無論何時要檢視索引的樹狀結構，可使用每一頁面的LFK與UFK來對一葉節點執行有效性檢查，就可很簡單地決定索引結構的錯誤。同樣地，由於葉節點間的連接關係是由LFK與UFK決定，可移除葉節點的連結(link)，藉此可提升結構變更運算(structure modification operation,SMO)的效能與效率。
如上述，根據本發明的一或更多個實施例，可節省一儲存該索引的頁面之儲存空間，並因此而提升DB的效能。
同樣地，根據本發明的一或更多個實施例，於執行時間(run-time)內可設定壓縮，在特定區域的插入/刪除運算的負荷高時不執行壓縮，因此可提升DB的運算效能。
同樣地，根據本發明的一或更多個實施例，不需要額外記錄有關二次壓縮方法與範圍的元資料，因此，當儲存在頁面內的記錄數目增加時，可提升壓縮效率。
同樣地，根據本發明的一或更多個實施例，無論何時要檢視索引的樹狀結構，可使用每一頁面的LFK與UFK對葉節點進行有效性檢查，因此可輕易地決定索引結構的錯誤。
上述的DB管理方法可寫成能夠用任何一種電腦執行的程式。在此，可用於執行DB管理方法的程式可以儲存在電腦可讀取記錄媒 體，像是硬碟、CD-ROM、DVD-ROM、RAM，或一快閃記憶體中。
儘管先前已參考圖表說明本發明，然而熟悉此技藝者應可了解在不違背以下的申請專利範圍所定義之本發明的精神與範疇的情形下，進行各種形式與細節的變化。
S100、S110、S120、S130‧‧‧步驟

Claims (20)

  1. 一種資料庫(database,DB)管理方法，包含：由一索引管理器儲存在每一頁面包括的複數個記錄的金鑰值的一下限值作為一下籬金鑰(lower fence key,LFK)，或複數個記錄的金鑰值的一上限值作為一上籬金鑰(upper fence key,UFK)；由該索引管理器萃取來自每一頁面包括的複數個記錄的金鑰值的一共同區域，作為一前置；以及由該索引管理器儲存從該複數個記錄的金鑰值去除對應該前置的一部分所取得的一剩餘部份，其中，該下籬金鑰以及該上籬金鑰是包含有該前置的原始金鑰值。
  2. 如請求項第1項所述之DB管理方法，其中該前置是儲存在該LFK或該UFK內。
  3. 如請求項第2項所述之DB管理方法，其中從該複數個記錄的原始金鑰值去除該前置所取得的金鑰值係儲存在記錄中，除了儲存該LFK或該UFK的地方之外。
  4. 如請求項第1項所述之DB管理方法，其中該複數個記錄的每一個係為一包含複數個金鑰值的多欄之形式。
  5. 如請求項第4項所述之DB管理方法，其中在該複數個金鑰值中的一金鑰值的一部份於形成一個頁面的記錄中均具有一相同數值，該金鑰值的一部分係被萃取為該前置。
  6. 如請求項第1項所述之DB管理方法，其中該些頁面的每一個頁面係一具有一B樹狀或B+樹狀結構之葉節點。
  7. 如請求項第1項所述之DB管理方法更包含由該索引管理器回復該些頁面的每一個頁面包括的該複數個記錄之原始金鑰值，其中該回復步驟包含： 決定該LFK與該UFK是否存在於一頁面內；如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該LFK與該UFK共同的一前置；以及藉由結合該被萃取的前置與一相關記錄的金鑰值回復原始金鑰值。
  8. 如請求項第7項所述之DB管理方法，其中如果該LFK與該UFK並不存在於該頁面內，則儲存在每一記錄內的金鑰值為原始金鑰值。
  9. 如請求項第1項所述之DB管理方法更包含由該索引管理器增加一新記錄至該些頁面的每一個頁面，或由該索引管理器更改一預存記錄，其中該增加或更改步驟包含：決定該LFK與該UFK是否存在於一頁面內；如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該LFK與該UFK共同的一前置；以及將一要增加的記錄去除該前置所取得的剩餘金鑰值增加至該頁面的一記錄，或將該頁面的該記錄更改為從一記錄去除該前置所取得的剩餘金鑰值以更換該頁面的該記錄。
  10. 如請求項第9項所述之DB管理方法，其中如果該LFK與該UFK並不存在於該頁面內，則不萃取該前置，以及將一新記錄增加至一頁面或更改該頁面的一預存記錄。
  11. 一種電腦可讀取記錄媒體，其具有一程式被記錄於其上以用於執行如請求項第1項所述之DB管理方法。
  12. 一種資料庫(DB)管理系統，包含：一接收與分析一查詢的查詢分析器，其中該查詢分析器係定義一用於被包括在一特定表內的記錄之取回要求與一用於至少一個被包括在該記錄內的欄之更新要求； 一執行計畫產生器，其產生一用於執行該被分析的查詢之執行計畫；一執行計畫執行單元，其根據該執行計畫取回該記錄與更新該至少一個欄以執行該執行計畫；以及一索引管理器，其包含一索引產生器，其產生一關於該特定表的索引，並儲存在該索引的每一頁面包括的複數個記錄的金鑰值之一下限值作為一下籬金鑰(lower fence key,LFK)，或複數個記錄的金鑰值的一上限值作為一上籬金鑰(upper fence key,UFK)；其中，該下籬金鑰以及該上籬金鑰是包含有一前置的原始金鑰值。
  13. 如請求項第12項所述之DB管理系統，其中該索引產生器萃取來自每一頁面包括的複數個記錄的金鑰值的一共同區域，作為一前置。
  14. 如請求項第13項所述之DB管理系統，其中該索引產生器儲存從該複數個記錄的金鑰值去除對應該前置的一部分所取得的一剩餘部份，該前置為每一頁面包括的複數個記錄的金鑰值的該共同區域。
  15. 如請求項第13項所述之DB管理系統，其中該前置僅被儲存在該LFK或該UFK內。
  16. 如請求項第15項所述之DB管理系統，其中從該複數個記錄的原始金鑰值去除該前置所取得的金鑰值係被儲存在記錄中，除了儲存該LFK或該UFK的地方之外。
  17. 如請求項第13項所述之DB管理系統，其中該索引管理器更包含一記錄回復器，其回復來自該索引的每一頁面包括的複數個記錄之原始金鑰值。
  18. 如請求項第17項所述之DB管理系統，其中該記錄回復器決定該LFK與該UFK是否存在於一頁面內；如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該前置；以及藉由結合該被萃取的前置與該頁面的一相關記錄的金鑰值以回復原始金鑰值。
  19. 如請求項第13項所述之DB管理系統，其中該索引管理器更包含一記錄更新器，其增加一新記錄至該索引的該些頁面的每一個頁 面，或更改一預存記錄。
  20. 如請求項第19項所述之DB管理系統，其中該記錄更新器決定該LFK與該UFK是否存在於一頁面內；如果該LFK與該UFK存在於該頁面內，比較該LFK與該UFK以萃取該前置；以及將一要增加的記錄去除該前置所取得的剩餘金鑰值增加至該頁面的一記錄，或將該頁面的該記錄更改為從一記錄去除該前置所取得的剩餘金鑰值以更換該頁面的該記錄。
TW103135611A 2013-10-15 2014-10-15 資料庫管理方法、資料庫管理系統，以及資料庫樹狀結構 TWI549009B (zh)

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020130122951A KR101549220B1 (ko) 2013-10-15 2013-10-15 데이터베이스 관리 방법, 시스템 및 데이터베이스 트리 구조

Publications (2)

Publication Number Publication Date
TW201514734A TW201514734A (zh) 2015-04-16
TWI549009B true TWI549009B (zh) 2016-09-11

Family

ID=52810565

Family Applications (1)

Application Number Title Priority Date Filing Date
TW103135611A TWI549009B (zh) 2013-10-15 2014-10-15 資料庫管理方法、資料庫管理系統，以及資料庫樹狀結構

Country Status (4)

Country Link
US (1) US10664459B2 (zh)
JP (1) JP5959592B2 (zh)
KR (1) KR101549220B1 (zh)
TW (1) TWI549009B (zh)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN106156197A (zh) * 2015-04-22 2016-11-23 中兴通讯股份有限公司 一种数据库的查询方法和装置
JP7237782B2 (ja) 2019-09-13 2023-03-13 キオクシア株式会社 ストレージシステム及びその制御方法
CN110716933B (zh) * 2019-09-29 2022-03-15 浙江大学 一种面向新型城轨列车大数据的高伸缩分布式索引方法
CN111008195A (zh) * 2019-10-31 2020-04-14 苏州浪潮智能科技有限公司 一种数据库空闲空间管理方法、系统、终端及存储介质
CN111367915A (zh) * 2020-03-04 2020-07-03 深圳前海微众银行股份有限公司 一种区块链数据的操作方法及装置
KR102127785B1 (ko) * 2020-03-11 2020-06-29 주식회사 티맥스티베로 효율적인 인덱싱을 제공하기 위한 방법, 장치 및 컴퓨터-판독가능 매체에 포함된 컴퓨터 프로그램
US12118107B2 (en) * 2021-05-27 2024-10-15 Intuit Inc. Detecting sensitive information in records using context and decoys
KR20230120347A (ko) * 2022-02-09 2023-08-17 주식회사 티맥스티베로 데이터를 인덱스하기 위한 방법

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20090164415A1 (en) * 2007-12-21 2009-06-25 Nhn Corporation Method and system for managing database
TW201228287A (en) * 2010-12-31 2012-07-01 Aten Int Co Ltd Remote management system and operating method thereof
US20130238576A1 (en) * 2012-03-09 2013-09-12 Nathan L. Binkert Validation of distributed balanced trees

Family Cites Families (13)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5812996A (en) * 1994-07-12 1998-09-22 Sybase, Inc. Database system with methods for optimizing query performance with a buffer manager
JPH09167111A (ja) * 1995-12-19 1997-06-24 Hitachi Ltd データベースのデータ格納方法
US6584459B1 (en) * 1998-10-08 2003-06-24 International Business Machines Corporation Database extender for storing, querying, and retrieving structured documents
US6804677B2 (en) * 2001-02-26 2004-10-12 Ori Software Development Ltd. Encoding semi-structured data for efficient search and browsing
US6694323B2 (en) * 2002-04-25 2004-02-17 Sybase, Inc. System and methodology for providing compact B-Tree
JP2004062475A (ja) * 2002-07-29 2004-02-26 Hitachi Ltd インデクス格納方法
US7693824B1 (en) * 2003-10-20 2010-04-06 Google Inc. Number-range search system and method
US8364711B2 (en) * 2006-05-09 2013-01-29 John Wilkins Contact management system and method
KR100834760B1 (ko) 2006-11-23 2008-06-05 삼성전자주식회사 최적화된 인덱스 검색 방법 및 장치
KR101160388B1 (ko) 2008-02-05 2012-06-26 엔에이치엔비즈니스플랫폼 주식회사 데이터베이스 관리 방법 및 시스템
US8255398B2 (en) * 2008-09-30 2012-08-28 International Business Machines Corporation Compression of sorted value indexes using common prefixes
US8055675B2 (en) 2008-12-05 2011-11-08 Yahoo! Inc. System and method for context based query augmentation
US8180763B2 (en) * 2009-05-29 2012-05-15 Microsoft Corporation Cache-friendly B-tree accelerator

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20090164415A1 (en) * 2007-12-21 2009-06-25 Nhn Corporation Method and system for managing database
TW201228287A (en) * 2010-12-31 2012-07-01 Aten Int Co Ltd Remote management system and operating method thereof
US20130238576A1 (en) * 2012-03-09 2013-09-12 Nathan L. Binkert Validation of distributed balanced trees

Also Published As

Publication number Publication date
KR20150043929A (ko) 2015-04-23
TW201514734A (zh) 2015-04-16
JP2015079508A (ja) 2015-04-23
US20150106380A1 (en) 2015-04-16
KR101549220B1 (ko) 2015-09-03
JP5959592B2 (ja) 2016-08-02
US10664459B2 (en) 2020-05-26

Similar Documents

Publication Publication Date Title
TWI549009B (zh) 資料庫管理方法、資料庫管理系統，以及資料庫樹狀結構
US10657116B2 (en) Create table for exchange
US10019284B2 (en) Method for performing transactions on data and a transactional database
US10180992B2 (en) Atomic updating of graph database index structures
US8924365B2 (en) System and method for range search over distributive storage systems
KR20170024039A (ko) 유연한 스키마를 사용한 데이터 관리
US20170255708A1 (en) Index structures for graph databases
US11782924B2 (en) Distributed join index for shared-nothing and log-structured databases
CN113867627B (zh) 一种存储系统性能优化方法及系统
JPWO2010084754A1 (ja) データベースシステム、データベース管理方法、及びデータベース構造
KR101238381B1 (ko) 다중범위 스캔에서의 ｎ 정렬 질의를 최적으로 처리하기 위한 방법 및 장치
Tzouramanis et al. Overlapping B+-trees: An implementation of a transaction time access method
US11520763B2 (en) Automated optimization for in-memory data structures of column store databases
US9594785B2 (en) Database management device and database management method
Carter et al. Nanosecond indexing of graph data with hash maps and VLists
US10572483B2 (en) Aggregate projection
KR102013839B1 (ko) 데이터베이스 관리 방법, 시스템 및 데이터베이스 트리 구조
Hu et al. Defining temporal operators for column oriented NoSQL databases
Hua et al. Efficient evaluation of traversal recursive queries using connectivity index
Jota et al. A physical design strategy on a nosql dbms
CN107145601A (zh) 一种高效的引用关系发现算法
Budalakoti et al. Automated Clustering Recommendation With Database Zone Maps
Sparse et al. Check for updates
Batra et al. Modeling sparse and evolving data
CN116028675A (zh) 一种亿级树结构记录表的树分拆方法