計(jì)算機(jī)數(shù)據(jù)恢復(fù)技術(shù) 課件 第1章 計(jì)算機(jī)數(shù)據(jù)恢復(fù)基礎(chǔ)

第1章

計(jì)算機(jī)數(shù)據(jù)恢復(fù)基礎(chǔ)1.1數(shù)據(jù)的表示方法

1.1.1計(jì)算機(jī)數(shù)據(jù)的含義計(jì)算機(jī)數(shù)據(jù)：

是指所有能輸入計(jì)算機(jī)并被計(jì)算機(jī)程序處理的符號(hào)的介質(zhì)的總稱，是輸入計(jì)算機(jī)后進(jìn)行處理并具有一定意義的數(shù)字、字母和模擬量等的通稱。數(shù)據(jù)（Data）需要解釋才能成為信息，要將數(shù)據(jù)轉(zhuǎn)換為信息，必須考慮幾個(gè)已知因素。所涉及的因素由數(shù)據(jù)的創(chuàng)建者和所需信息決定。元數(shù)據(jù)是用于引用有關(guān)數(shù)據(jù)的數(shù)據(jù)。元數(shù)據(jù)可以間接或直接地被指定或給定。計(jì)算機(jī)數(shù)據(jù)簡(jiǎn)單來(lái)說(shuō)就是能被計(jì)算機(jī)識(shí)別、處理且存儲(chǔ)在計(jì)算機(jī)設(shè)備中的數(shù)據(jù)。計(jì)算機(jī)數(shù)據(jù)涉及的領(lǐng)域有數(shù)據(jù)維護(hù)和恢復(fù)、數(shù)據(jù)安全等。1．進(jìn)位計(jì)數(shù)制我們所使用的計(jì)算機(jī)均為馮·諾依曼型計(jì)算機(jī)，且其內(nèi)部使用二進(jìn)制來(lái)表示數(shù)據(jù)。數(shù)制也稱計(jì)數(shù)制，是指用一組固定的符號(hào)和統(tǒng)一的規(guī)則來(lái)表示數(shù)值的方法。

在日常生活中，人們最常用的進(jìn)位計(jì)數(shù)制是十進(jìn)制，即按照“逢十進(jìn)一”的原則進(jìn)行計(jì)數(shù)。但在實(shí)際應(yīng)用中，常會(huì)用到其他的進(jìn)位計(jì)數(shù)制，如二進(jìn)制、八進(jìn)制、十六進(jìn)制、六十進(jìn)制等。進(jìn)位計(jì)數(shù)制的特點(diǎn)是通過(guò)一組規(guī)定的數(shù)字來(lái)表示任意的數(shù)。

例如，一個(gè)二進(jìn)制數(shù)只能用0和1來(lái)表示，一個(gè)十進(jìn)制數(shù)只能用0～9來(lái)表示，一個(gè)十六進(jìn)制數(shù)只能用0～9和A～F這16個(gè)數(shù)碼來(lái)表示。一種進(jìn)位計(jì)數(shù)制包含一組數(shù)碼和3個(gè)基本因素（基數(shù)、數(shù)位、權(quán)）。1．進(jìn)位計(jì)數(shù)制（1）數(shù)碼。一組用來(lái)表示某種進(jìn)位計(jì)數(shù)制的符號(hào)。例如，十進(jìn)制的數(shù)碼是0、1、

2、3、4、5、6、7、8、9；二進(jìn)制的數(shù)碼是0、1。（2）基數(shù)。某進(jìn)位計(jì)數(shù)制可以使用的數(shù)碼個(gè)數(shù)。例如，十進(jìn)制的基數(shù)是10，二

進(jìn)制的基數(shù)是2。（3）數(shù)位。數(shù)碼在一個(gè)數(shù)中所處的位置。（4）權(quán)。權(quán)是基數(shù)的冪，表示數(shù)碼在不同位置上的數(shù)值。

在基數(shù)為J的進(jìn)位計(jì)數(shù)制中，包含J個(gè)不同的數(shù)碼，每個(gè)數(shù)位計(jì)滿J就向高位進(jìn)1，即“逢

J進(jìn)一”。1．進(jìn)位計(jì)數(shù)制

一個(gè)數(shù)碼處在不同數(shù)位時(shí)，所表示的數(shù)值是不同的。每個(gè)數(shù)碼所表示的數(shù)值等于該數(shù)碼乘以一個(gè)與數(shù)碼所在數(shù)位有關(guān)的常數(shù)，這個(gè)常數(shù)稱為位權(quán)，簡(jiǎn)稱權(quán)。權(quán)的大小是以基數(shù)為底，以數(shù)碼所在位置的序號(hào)為指數(shù)的整數(shù)次冪。例如，十進(jìn)制數(shù)的百分位、十分位、個(gè)位、十位、百位、千位的權(quán)依次是：10-2、10-1、100、101、102、103。一個(gè)

J進(jìn)制數(shù)(S)J按權(quán)展開(kāi)的多項(xiàng)式和的一般表達(dá)式為：2．二進(jìn)制

二進(jìn)制是在計(jì)算機(jī)技術(shù)中被廣泛采用的一種數(shù)制。二進(jìn)制數(shù)是用0和1兩個(gè)數(shù)碼來(lái)表示的。它的基數(shù)為2，進(jìn)位規(guī)則是“逢二進(jìn)一”，借位規(guī)則是“借一當(dāng)二”。當(dāng)前的計(jì)算機(jī)系統(tǒng)使用的數(shù)制基本均為二進(jìn)制。計(jì)算機(jī)內(nèi)部采用二進(jìn)制的原因主要有以下幾點(diǎn)：（1）技術(shù)實(shí)現(xiàn)簡(jiǎn)單。（2）運(yùn)算規(guī)則簡(jiǎn)單。（3）適合邏輯運(yùn)算。（4）易于進(jìn)行轉(zhuǎn)換。（5）具有抗干擾能力強(qiáng)，可靠性高等優(yōu)點(diǎn)。2．二進(jìn)制

二進(jìn)制的基數(shù)為2，只有“0”和“1”兩個(gè)數(shù)碼。二進(jìn)制在計(jì)數(shù)時(shí)“逢二進(jìn)一”，第i位的權(quán)是2的i次冪。一個(gè)二進(jìn)制數(shù)展開(kāi)成多項(xiàng)式和的表達(dá)式為：例如，（1101.011）2=1×23+1×22+0×21+1×20+0×2-1+1×2-2+1×2-3。

十六進(jìn)制的基數(shù)為16，有0、1、2、3、4、5、6、7、8、9及大寫英文字母A、B、C、D、E、F（數(shù)碼A~F對(duì)應(yīng)十進(jìn)制數(shù)分別是10~15）共16個(gè)數(shù)碼。十六進(jìn)制在計(jì)數(shù)時(shí)“逢十六進(jìn)一”，第i位上的權(quán)是16的i次冪。一個(gè)十六進(jìn)制數(shù)展開(kāi)成多項(xiàng)式和的表達(dá)式為：2．二進(jìn)制

十進(jìn)制數(shù)、十六進(jìn)制數(shù)和二進(jìn)制數(shù)之間有著非常簡(jiǎn)單的對(duì)應(yīng)關(guān)系。3種常用進(jìn)位計(jì)數(shù)制數(shù)的對(duì)照表如表1-1所示。十進(jìn)制數(shù)二進(jìn)制數(shù)十六進(jìn)制數(shù)十進(jìn)制數(shù)二進(jìn)制數(shù)十六進(jìn)制數(shù)00081000811191001921021010l0A3113111011B41004121l00C51015131101D61106141110E71117151111F3．進(jìn)位計(jì)數(shù)制數(shù)的相互轉(zhuǎn)換1）二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)

若想將二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)，只需要把二進(jìn)制數(shù)寫成按權(quán)展開(kāi)多項(xiàng)式和的形式，再計(jì)算此表達(dá)式的和即可。例如：1101B=1×23+1×22+0×21+1×20=23+22+20=13D。

為了使進(jìn)位計(jì)數(shù)制數(shù)表述清晰、方便，常在其后面加上大寫字母加以區(qū)別：加字母B（Blnary）表示二進(jìn)制數(shù)；加字母O（Octal）表示八進(jìn)制數(shù)；加字母H（Hexadecimal）表示十六進(jìn)制數(shù)；加字母D（Decimal）或不加字母表示十進(jìn)制數(shù)。3．進(jìn)位計(jì)數(shù)制數(shù)的相互轉(zhuǎn)換2）十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)

如果十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制整數(shù)，則采用“除2取余”法。其規(guī)則：除2取余，直至商為0，再進(jìn)行倒排，即將十進(jìn)制整數(shù)除以2，得到一個(gè)商和一個(gè)余數(shù)，再將商除以2，又得到一個(gè)商和一個(gè)余數(shù)，以此類推，直至商為0，再將每次得到的余數(shù)倒序排列，就是對(duì)應(yīng)的二進(jìn)制整數(shù)。例如，將十進(jìn)制整數(shù)86轉(zhuǎn)換成二進(jìn)制整數(shù)：即86D=(k6

k5

k4

k3

k2

k1

k0)=1010110B。3．進(jìn)位計(jì)數(shù)制數(shù)的相互轉(zhuǎn)換3）十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)

如果十進(jìn)制小數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)，則采用“乘2取整”法。其規(guī)則：乘2取整，直至小數(shù)部分為0或給定的精度，再進(jìn)行順排，即用2逐次去乘十進(jìn)制小數(shù)，將每次得到的積的整數(shù)部分按各自出現(xiàn)的先后順序依次排列，即可得到對(duì)應(yīng)的二進(jìn)制小數(shù)。

例如，將十進(jìn)制小數(shù)0.875轉(zhuǎn)換成二進(jìn)制小數(shù)：即0.875D=(k-1

k-2

k-3)=0.111B。3．進(jìn)位計(jì)數(shù)制數(shù)的相互轉(zhuǎn)換4）十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)

十六進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)的規(guī)則：將每一位十六進(jìn)制數(shù)改寫成等值的4位二進(jìn)制數(shù)，次序不變。

例如，將十六進(jìn)制數(shù)1CA.BH轉(zhuǎn)換成二進(jìn)制數(shù)：1CA.B000111001010.1011即1CA.BH=000111001010.1011B=111001010.1011B。3．進(jìn)位計(jì)數(shù)制數(shù)的相互轉(zhuǎn)換5）二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)將二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)的規(guī)則：（1）整數(shù)部分從最低有效位開(kāi)始，以4位為一組，含最高有效位的一組不足4位時(shí)以0補(bǔ)齊，每一組二進(jìn)制數(shù)均可轉(zhuǎn)換成一個(gè)十六進(jìn)制數(shù)，各組轉(zhuǎn)換完畢后即可得到轉(zhuǎn)換后的十六進(jìn)制整數(shù)。

（2）小數(shù)部分從最高有效位開(kāi)始，以4位為一組，含最低有效位的一組不足4位時(shí)以0補(bǔ)齊，每一組二進(jìn)制數(shù)均可轉(zhuǎn)換成一個(gè)十六進(jìn)制數(shù)，各組轉(zhuǎn)換完畢后即可得到轉(zhuǎn)換后的十六進(jìn)制小數(shù)。例如，將二進(jìn)制數(shù)11001111.01111B轉(zhuǎn)換成十六進(jìn)制數(shù)：

84218421.84218421

11001111.01111

C

F

.7

8即11001111.01111B=CF.78H。1.1.2數(shù)值數(shù)據(jù)在計(jì)算機(jī)中的表示方法

計(jì)算機(jī)只能識(shí)別二進(jìn)制數(shù)，而要求計(jì)算機(jī)處理的數(shù)卻種類繁多，這該怎么辦呢？在計(jì)算機(jī)中，各種形式的編碼很好地解決了數(shù)及字符等信息的表示問(wèn)題。

數(shù)據(jù)可分為兩大類：數(shù)值數(shù)據(jù)和非數(shù)值數(shù)據(jù)。前者表示數(shù)量的多少；后者表示字符、漢字、圖形、圖像、聲音等數(shù)據(jù)，又稱符號(hào)數(shù)據(jù)。在計(jì)算機(jī)內(nèi)，無(wú)論哪一種數(shù)據(jù)，都以二進(jìn)制的形式來(lái)表示。1．?dāng)?shù)據(jù)的單位數(shù)據(jù)的常用單位有位、字節(jié)和字。1）位（Bit）

在計(jì)算機(jī)中，最小的數(shù)據(jù)單位是二進(jìn)制的一個(gè)數(shù)位，簡(jiǎn)稱位（英文名稱為Bit，讀音為“比特”）。一位二進(jìn)制數(shù)只具有“0”和“1”兩個(gè)狀態(tài)。在計(jì)算機(jī)中，最直接和最基本的操作就是對(duì)二進(jìn)制位的操作。

字節(jié)（Byte，B）是計(jì)算機(jī)信息技術(shù)用于計(jì)量存儲(chǔ)量的一種計(jì)量單位。字節(jié)這一名詞專門用來(lái)表示8位二進(jìn)制數(shù)。

作為一個(gè)8位二進(jìn)制數(shù)，一個(gè)字節(jié)可以從00000000取值到11111111，可以表示0~255的正數(shù)，也可以表示-128～127的正、負(fù)數(shù)?？傊粋€(gè)特定的字節(jié)可以代表28（即256種）不同事物中的一種。

2）字節(jié)（Byte）

在計(jì)算機(jī)中，作為一個(gè)整體被存取、傳送、處理的二進(jìn)制數(shù)串稱為一個(gè)“字”或“單元”。字通?？煞譃槿舾蓚€(gè)字節(jié)。在存儲(chǔ)器中，通常情況下每個(gè)單元存儲(chǔ)一個(gè)字。因此，每個(gè)字都是可以尋址的。字的長(zhǎng)度用位數(shù)來(lái)表示。1．?dāng)?shù)據(jù)的單位3）字（Word）2．字長(zhǎng)

在字中，二進(jìn)制位數(shù)的長(zhǎng)度稱為字長(zhǎng)。根據(jù)計(jì)算機(jī)的不同，字長(zhǎng)有固定的和可變的兩種。固定字長(zhǎng)，即字的長(zhǎng)度無(wú)論在什么情況下都是固定不變的；可變字長(zhǎng)，即其長(zhǎng)度在一定范圍內(nèi)是可變的。

計(jì)算機(jī)的字長(zhǎng)是指計(jì)算機(jī)一次可處理的二進(jìn)制數(shù)的長(zhǎng)度。計(jì)算機(jī)處理數(shù)據(jù)的速率和它一次處理的信息位數(shù)以及其進(jìn)行運(yùn)算的快慢有關(guān)。如果一臺(tái)計(jì)算機(jī)的字長(zhǎng)是另一臺(tái)計(jì)算機(jī)的兩倍，兩臺(tái)計(jì)算機(jī)的運(yùn)算速度相同，在相同的時(shí)間內(nèi)，前者能做的工作是后者的兩倍。

在微型計(jì)算機(jī)中，通常用字節(jié)來(lái)表示存儲(chǔ)器的存儲(chǔ)容量。在計(jì)算機(jī)的運(yùn)算器和控制器中，數(shù)據(jù)通常是以字為單位進(jìn)行傳送的。另外，字在不同的地址中出現(xiàn)其含義是不相同的。例如，送往控制器的字是指令，而送往運(yùn)算器的字就僅是一個(gè)數(shù)。一個(gè)字由若干個(gè)字節(jié)組成。不同計(jì)算機(jī)系統(tǒng)的字長(zhǎng)也是不同的，常見(jiàn)的有8位、16位、32位、64位等。字長(zhǎng)越長(zhǎng)，計(jì)算機(jī)一次處理的信息位就越多，精度就越髙。字長(zhǎng)是計(jì)算機(jī)性能的一個(gè)重要指標(biāo)。在一般情況下，大型計(jì)算機(jī)的字長(zhǎng)為32～64位，小型計(jì)算機(jī)的字長(zhǎng)為12～32位，而微型計(jì)算機(jī)的字長(zhǎng)為4～16位。字長(zhǎng)是衡量計(jì)算機(jī)性能的一個(gè)重要因素。1.1.3字符數(shù)據(jù)在計(jì)算機(jī)中的表示方法

在計(jì)算機(jī)領(lǐng)域中，數(shù)據(jù)的概念是廣義的。計(jì)算機(jī)除了處理各種數(shù)值之外，還要處理大量的符號(hào)，如英文字母和漢字等非數(shù)值信息。例如，當(dāng)要用計(jì)算機(jī)編寫文章時(shí)，就需要將文章中的各種符號(hào)、英文字母和漢字等字符輸入計(jì)算機(jī)，然后由計(jì)算機(jī)進(jìn)行編輯和排版。

計(jì)算機(jī)中的數(shù)據(jù)可以分為數(shù)值數(shù)據(jù)與非數(shù)值數(shù)據(jù)兩種。其中，數(shù)值數(shù)據(jù)就是常說(shuō)的“數(shù)”（如整數(shù)、實(shí)數(shù)等），且在計(jì)算機(jī)中是以二進(jìn)制數(shù)的形式存放的；而非數(shù)值數(shù)據(jù)與一般的“數(shù)”不同，通常不表示數(shù)值大小，只表示字符或圖形等信息，但這些信息在計(jì)算機(jī)中也是以二進(jìn)制數(shù)的形式存放的。美國(guó)信息交換標(biāo)準(zhǔn)代碼（AmericanStandardCodeforInformationInterchange，ASCII）是基于拉丁字母的一套計(jì)算機(jī)編碼系統(tǒng)，也是國(guó)際通用的信息交換標(biāo)準(zhǔn)。ASCII使用指定的7位或8位二進(jìn)制數(shù)的組合來(lái)表示128種或256種可能的字符。用ASCII表示的字符稱為ASCII字符。如表1-2所示為ASCII編碼表。1.1.3字符數(shù)據(jù)在計(jì)算機(jī)中的表示方法

0000010100111001011101110000NULDELSP0@P0‘p0001SOHDC1!1AQaq0010STXDC2“2BRbr0011ETXDC3#3CSCs0100EOTDC4$4DTdt0101ENQNAK%5EUeU0110ACKSYN&6FVfV0111DELETB

7GWgW1000BSCAN（8HXhx1001HTEM）9IYiy1010LFSUB*：JZjz1011VTESC+；K[k{1100FFFS，<

L\ll1101CRGS-=M]m}1110S0RS.>

N

n-1111SIUS/?O_oDEL1.2數(shù)據(jù)的邏輯運(yùn)算

邏輯運(yùn)算又稱布爾運(yùn)算。英國(guó)的數(shù)學(xué)家布爾，在1847年發(fā)明了處理二值之間關(guān)系的邏輯數(shù)學(xué)計(jì)算法。他用等式表示判斷，把推理看成等式的變換。這種變換的有效性不依賴于人們對(duì)符號(hào)的認(rèn)識(shí)，只依賴于符號(hào)的組合規(guī)律。20世紀(jì)30年代，邏輯代數(shù)在電路系統(tǒng)中得到應(yīng)用。之后，隨著電子技術(shù)與計(jì)算機(jī)的發(fā)展，出現(xiàn)了各種復(fù)雜的系統(tǒng)。這些系統(tǒng)的變換規(guī)律也遵守布爾所揭示的規(guī)律。

邏輯運(yùn)算是CPU運(yùn)算的本質(zhì)。計(jì)算機(jī)在處理無(wú)論多么復(fù)雜的事情時(shí)，都得通過(guò)電路的開(kāi)關(guān)。邏輯是指對(duì)某個(gè)事物的推理，有“真”和“假”是兩個(gè)對(duì)立的邏輯狀態(tài)。邏輯運(yùn)算是指用數(shù)學(xué)符號(hào)來(lái)表示邏輯狀態(tài)，以便于用數(shù)學(xué)方法研究邏輯問(wèn)題。1.2數(shù)據(jù)的邏輯運(yùn)算

在計(jì)算機(jī)中進(jìn)行的運(yùn)算是二進(jìn)制運(yùn)算，邏輯判斷的結(jié)果只有兩個(gè)值，這兩個(gè)值稱為“邏輯值”，用數(shù)碼來(lái)表示就是“1”和“0”。其中，“1”表示該邏輯運(yùn)算的結(jié)果為“真”，“0”表示該邏輯運(yùn)算的結(jié)果為“假”。我們常將電路通電狀態(tài)表示為“真”，用數(shù)字“1”表示，不通電狀態(tài)表示為“假”，用數(shù)字“0”表示。

計(jì)算機(jī)的邏輯運(yùn)算與算術(shù)運(yùn)算的主要區(qū)別：邏輯運(yùn)算是按位進(jìn)行的，位與位之間不像加/減運(yùn)算那樣有進(jìn)位或借位的聯(lián)系。

邏輯運(yùn)算主要包括3種基本運(yùn)算：“或”運(yùn)算、“與”運(yùn)算和“非”運(yùn)算。此外，還有一種“異或”運(yùn)算也很有用。在磁盤陣列（redundantarrayofindependentdisks，簡(jiǎn)寫為RAID）中，就會(huì)大量使用“異或”運(yùn)算作為校驗(yàn)算法。1.2.1“或”運(yùn)算

“或”運(yùn)算又稱加運(yùn)算，運(yùn)算符號(hào)有“+”“V”“OR”等。

“或”邏輯是指當(dāng)輸入變量中有一個(gè)變量滿足條件時(shí)，輸出結(jié)果就有效。只有當(dāng)所有輸入變量均不滿足條件時(shí)，輸出結(jié)果才無(wú)效。

也就是說(shuō)，在給定的邏輯變量中，只要有一個(gè)變量為1，其運(yùn)算結(jié)果為1；當(dāng)邏輯變量都為0時(shí)，運(yùn)算結(jié)果為0。其運(yùn)算規(guī)則如下：0+0=0，0∨0=00+1=1，0∨1=11+0=1，1∨0=11+1=1，1∨1=1例如，x=10110011、y=10011011，求x∨y。即x∨y=10111011B1.2.2“與”運(yùn)算

“與”運(yùn)算又稱乘運(yùn)算，運(yùn)算符號(hào)有“x”“^”“.”等。

“與”邏輯是指當(dāng)所有輸入變量同時(shí)滿足條件時(shí)，輸出結(jié)果才有效，否則輸出結(jié)果無(wú)效。

也就是說(shuō)，只有當(dāng)參與運(yùn)算的邏輯變量同時(shí)取值為1時(shí)，其運(yùn)算結(jié)果才等于1。其運(yùn)算規(guī)則如下：0x0=0,0∧0=0,0?0=00x1=0,0∧1=0,0?1=01x0=0,1∧0=0,1?0=01x1=1,1∧1=1,1?1=1例如，x=10110011、y=10011011，求x∧y。即x∧y=10010011B1.2.3“非”運(yùn)算

“非”運(yùn)算又稱反運(yùn)算，運(yùn)算符號(hào)為在變量上畫一條橫線。

“非”邏輯是指當(dāng)輸入變量為1時(shí)，輸出結(jié)果為0；當(dāng)輸入變量為0時(shí)，輸出結(jié)果為1。也就是說(shuō)，0的非為1，1的非為0。1.2.4“異或”運(yùn)算

“異或”邏輯表示兩個(gè)值不同為“真”、“相同”為假。也就是說(shuō)，兩個(gè)值都為0或者1，其運(yùn)算結(jié)果為0；而一個(gè)值為0，另一個(gè)值為1，其運(yùn)算結(jié)果為1?！爱惢颉边\(yùn)算通常用符號(hào)“⊕”表示，其運(yùn)算規(guī)則如下：0⊕0=00⊕1=11⊕0=11⊕1=0例如，x=10110011、y=10011011，求x⊕y。即x⊕y=00101000B1.3數(shù)據(jù)結(jié)構(gòu)

如果想深入掌握數(shù)據(jù)恢復(fù)技術(shù)，就不能缺少對(duì)數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，因?yàn)樵跀?shù)據(jù)的存儲(chǔ)和管理中處處離不開(kāi)數(shù)據(jù)結(jié)構(gòu)，如硬盤的分區(qū)結(jié)構(gòu)、文件的系統(tǒng)結(jié)構(gòu)等，都是對(duì)數(shù)據(jù)結(jié)構(gòu)的具體應(yīng)用。1.3.1數(shù)據(jù)結(jié)構(gòu)的概念與分類

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科中的一門專業(yè)課程，更是在程序設(shè)計(jì)中不可或缺的一部分。數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。在通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行和存儲(chǔ)效率。數(shù)據(jù)結(jié)構(gòu)往往與高效的檢索算法和索引技術(shù)有關(guān)。1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念1）什么是數(shù)據(jù)

數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)是指所有能被輸入計(jì)算機(jī)，且能被計(jì)算機(jī)處理的符號(hào)（數(shù)字、字符等）的集合，是計(jì)算機(jī)操作對(duì)象的總稱。1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念2）數(shù)據(jù)元素

數(shù)據(jù)元素是在數(shù)據(jù)集合中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)的基本單位。

數(shù)據(jù)元素有兩類，一類是不可分割的“原子”型數(shù)據(jù)元素，如數(shù)值“1”、字符“N”等；另一類是由多個(gè)款項(xiàng)構(gòu)成的數(shù)據(jù)元素。其中每個(gè)款項(xiàng)稱為一個(gè)“數(shù)據(jù)項(xiàng)”。

關(guān)鍵字是指能識(shí)別一個(gè)或多個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)。若能起唯一識(shí)別作用，則稱為“主關(guān)鍵字”，否則稱為“次關(guān)鍵字”。3）關(guān)鍵字

數(shù)據(jù)對(duì)象是具有相同特性的數(shù)據(jù)元素的集合，如整數(shù)、實(shí)數(shù)等。數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集D。4）數(shù)據(jù)對(duì)象1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念5）數(shù)據(jù)結(jié)構(gòu)

若特性相同的數(shù)據(jù)元素集合中的數(shù)據(jù)元素間存在一種或多種特定的關(guān)系，則該數(shù)據(jù)元素集合稱為“數(shù)據(jù)結(jié)構(gòu)”。也就是說(shuō)，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”即指數(shù)據(jù)元素之間存在的關(guān)系。2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類1）按照數(shù)據(jù)結(jié)構(gòu)的關(guān)系分類數(shù)據(jù)結(jié)構(gòu)按照數(shù)據(jù)結(jié)構(gòu)的關(guān)系可分為線性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)和集合結(jié)構(gòu)。（1）線性結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系，如圖1-1所示。（2）樹(shù)結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系，如圖1-2所示。

圖1-2樹(shù)結(jié)構(gòu)

圖1-1線性結(jié)構(gòu)2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類1）按照數(shù)據(jù)結(jié)構(gòu)的關(guān)系分類（3）圖結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系，如圖1-3所示。（4）集合結(jié)構(gòu)是指數(shù)據(jù)結(jié)構(gòu)中的元素間除了“同屬一個(gè)集合”的相互關(guān)系外無(wú)其他關(guān)系，如圖1-4所示。

圖1-3圖結(jié)構(gòu)圖1-4集合結(jié)構(gòu)2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類2）按照數(shù)據(jù)結(jié)構(gòu)的層次分類（1）邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，可以用一個(gè)數(shù)據(jù)元素的集合來(lái)定義在此集合上的若干關(guān)系。其中，邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與其在計(jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。

（2）物理結(jié)構(gòu)又稱存儲(chǔ)結(jié)構(gòu)，是指數(shù)據(jù)結(jié)構(gòu)中的元素在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。①數(shù)據(jù)元素的機(jī)內(nèi)表示：用二進(jìn)制的位串表示數(shù)據(jù)元素。

②關(guān)系的機(jī)內(nèi)表示：數(shù)據(jù)元素間關(guān)系的機(jī)內(nèi)表示可以分為順序映像和非順序映像。

一般來(lái)說(shuō)，一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以根據(jù)需要表示成多種存儲(chǔ)結(jié)構(gòu)。常用的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引存儲(chǔ)和散列存儲(chǔ)結(jié)構(gòu)。順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：借助數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)：借助指示數(shù)據(jù)元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。2．?dāng)?shù)據(jù)結(jié)構(gòu)的分類2）按照數(shù)據(jù)結(jié)構(gòu)的層次分類（1）順序存儲(chǔ)結(jié)構(gòu)：（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（3）索引存儲(chǔ)結(jié)構(gòu)（4）散列存儲(chǔ)結(jié)構(gòu)1.3.2樹(shù)結(jié)構(gòu)1.樹(shù)結(jié)構(gòu)的定義

樹(shù)結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，它是由n（n≥1）個(gè)有限節(jié)點(diǎn)組成的具有層次關(guān)系的集合。在樹(shù)結(jié)構(gòu)中，用一個(gè)圓圈表示一個(gè)節(jié)點(diǎn)，圓圈內(nèi)的符號(hào)代表該節(jié)點(diǎn)的數(shù)據(jù)信息，節(jié)點(diǎn)之間的關(guān)系通過(guò)有方向的連線表示。其方向?yàn)閺纳舷蛳?，即上方?jié)點(diǎn)是下方節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，下方節(jié)點(diǎn)是上方節(jié)點(diǎn)的后繼節(jié)點(diǎn)。樹(shù)結(jié)構(gòu)（簡(jiǎn)稱樹(shù)）看起來(lái)像一棵倒掛的樹(shù)，如下圖所示。1.3.2樹(shù)結(jié)構(gòu)2．樹(shù)結(jié)構(gòu)的基本術(shù)語(yǔ)

（1）節(jié)點(diǎn)

（9）堂兄弟節(jié)點(diǎn)

（2）節(jié)點(diǎn)的度

（10）祖先節(jié)點(diǎn)

（3）樹(shù)的度

（11）子孫節(jié)點(diǎn)

（4）葉節(jié)點(diǎn)（終端節(jié)點(diǎn)）

（12）節(jié)點(diǎn)的層次

（5）分支節(jié)點(diǎn)（非終端節(jié)點(diǎn)）

（13）樹(shù)的高（深）度

（6）子女節(jié)點(diǎn)

（14）有序樹(shù)

（7）雙親節(jié)點(diǎn)

（15）無(wú)序樹(shù)

（8）兄弟節(jié)點(diǎn)

（16）森林1.3.2樹(shù)結(jié)構(gòu)3．樹(shù)結(jié)構(gòu)的特點(diǎn)（1）每個(gè)節(jié)點(diǎn)有0個(gè)或多個(gè)子節(jié)點(diǎn)。（2）每個(gè)子節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)。（3）沒(méi)有前驅(qū)節(jié)點(diǎn)作為根節(jié)點(diǎn)。（4）除了根節(jié)點(diǎn)外，每個(gè)子節(jié)點(diǎn)可以分為m個(gè)不相交的子樹(shù)。1.3.3樹(shù)結(jié)構(gòu)1．二叉樹(shù)的定義

二叉樹(shù)是樹(shù)形結(jié)構(gòu)的一種，只要對(duì)樹(shù)的結(jié)構(gòu)加以限制就能得到二叉樹(shù)。

二叉樹(shù)是n（n≥0）個(gè)節(jié)點(diǎn)的有限集合，并且滿足下面的任意一個(gè)條件。（1）為空二叉樹(shù)，即n=0。（2）由一個(gè)根節(jié)點(diǎn)和兩個(gè)互不相交的左子樹(shù)和右子樹(shù)組成。左子樹(shù)和右子樹(shù)的順序不能任意顛倒。如圖1-6所示的（a）和（b）就是兩個(gè)完全不同的二叉樹(shù)。1.3.3樹(shù)結(jié)構(gòu)2．樹(shù)和二叉樹(shù)的區(qū)別

（1）樹(shù)的節(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)可以為0。

（2）樹(shù)節(jié)點(diǎn)對(duì)最大度數(shù)沒(méi)有限制，而二叉樹(shù)節(jié)點(diǎn)的最大度數(shù)為2。

（3）樹(shù)的節(jié)點(diǎn)無(wú)左、右之分，而二叉樹(shù)的節(jié)點(diǎn)有左、右之分。1.3.3樹(shù)結(jié)構(gòu)3．二叉樹(shù)的基本形態(tài)（1）空二叉樹(shù)，如圖1-7所示。（2）僅有根節(jié)點(diǎn)的二叉樹(shù)，如圖1-8所示。（3）右子樹(shù)為空的二叉樹(shù)，如圖1-9所示。（4）左子樹(shù)為空的二叉樹(shù)，如圖1-10所示。（5）左、右子樹(shù)均為非空的二叉樹(shù)，如圖1-11所示。

圖1-8僅有根節(jié)點(diǎn)的二叉樹(shù)

圖1-7空二叉樹(shù)

圖1-9右子樹(shù)為空的二叉樹(shù)

圖1-10左子樹(shù)為空二叉樹(shù)

圖1-11左、右子樹(shù)均為空的二叉樹(shù)1.3.3樹(shù)結(jié)構(gòu)4．二叉樹(shù)的類型

（1）滿二叉樹(shù)。滿二叉樹(shù)是指除了葉節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都有左、右子女節(jié)點(diǎn)，且葉節(jié)點(diǎn)都處在最底層的二叉樹(shù)，如圖1-12所示。

（2）完全二叉樹(shù)。完全二叉樹(shù)是指除最后一層，每層的節(jié)點(diǎn)數(shù)均達(dá)到最大值，且在最后一層上只缺少右邊的若干節(jié)點(diǎn)的二叉樹(shù)，如圖1-13所示。

圖1-12滿二叉樹(shù)

圖1-13完全二叉樹(shù)1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)1．B樹(shù)1）B樹(shù)的定義B樹(shù)就是二叉查找樹(shù)，需要滿足下列條件。（1）所有非葉節(jié)點(diǎn)最多擁有兩個(gè)子女節(jié)點(diǎn)（左子女節(jié)點(diǎn)和右子女節(jié)點(diǎn)）。（2）所有節(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字。（3）非葉節(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹(shù)，右指針指向大于其關(guān)鍵字的子樹(shù)。如圖1-14所示的樹(shù)就是一個(gè)B樹(shù)。

圖1-14B樹(shù)

1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)1．B樹(shù)

2）B樹(shù)的查找B樹(shù)的查找是從根節(jié)點(diǎn)開(kāi)始，如果查找的關(guān)鍵字與節(jié)點(diǎn)關(guān)鍵字相等，那么該節(jié)點(diǎn)關(guān)鍵字即為查找的關(guān)鍵字；如果查找的關(guān)鍵字比節(jié)點(diǎn)關(guān)鍵字小，就進(jìn)入左子女節(jié)點(diǎn)；如果查找的關(guān)鍵字比節(jié)點(diǎn)關(guān)鍵字大，就進(jìn)入右子女節(jié)點(diǎn)；如果左子女節(jié)點(diǎn)或右子女節(jié)點(diǎn)的指針為空，則報(bào)告找不到相應(yīng)的關(guān)鍵字。

1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)2．

B-樹(shù)

1）B-樹(shù)的定義

B-樹(shù)是一種平衡的多叉樹(shù)。通常，m階的B-樹(shù)必須滿足下列條件。（1）每個(gè)節(jié)點(diǎn)最多擁有m個(gè)子女節(jié)點(diǎn)。（2）除根節(jié)點(diǎn)和葉節(jié)點(diǎn)外，其他的每個(gè)節(jié)點(diǎn)至少有m/2個(gè)子女節(jié)點(diǎn)。（3）若根節(jié)點(diǎn)不是葉節(jié)點(diǎn)，則至少有兩個(gè)子女節(jié)點(diǎn)。（4）所有的葉節(jié)點(diǎn)在同一層，且葉節(jié)點(diǎn)不包含任何關(guān)鍵字信息。（5）有k個(gè)子節(jié)點(diǎn)的非終端節(jié)點(diǎn)最多包含k-1個(gè)關(guān)鍵字信息

圖1-15B-樹(shù)1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)2．

B-樹(shù)

2）B-樹(shù)的查找B-樹(shù)的查找是一個(gè)順指針查找節(jié)點(diǎn)和在節(jié)點(diǎn)內(nèi)的關(guān)鍵字中查找交叉進(jìn)行的過(guò)程。從根節(jié)點(diǎn)開(kāi)始，在節(jié)點(diǎn)包含的關(guān)鍵字中查找給定的關(guān)鍵字，找到則查找成功；否則確定給定關(guān)鍵字可能存在的子樹(shù)，重復(fù)以上操作，直到查找成功或者指針為空為止。1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)2．

B-樹(shù)

3）B-樹(shù)的插入B-樹(shù)的插入首先是在恰當(dāng)?shù)娜~節(jié)點(diǎn)中添加關(guān)鍵字。如果在該節(jié)點(diǎn)中關(guān)鍵字不超過(guò)m-1個(gè)，則插入成功；否則要把這個(gè)節(jié)點(diǎn)分裂為兩個(gè)，并把中間的一個(gè)關(guān)鍵字拿出來(lái)插到節(jié)點(diǎn)的父節(jié)點(diǎn)中。當(dāng)插入父節(jié)點(diǎn)失敗時(shí)，就需要將父節(jié)點(diǎn)再分裂，繼續(xù)進(jìn)行插入操作。當(dāng)需要分裂根節(jié)點(diǎn)時(shí)，由于根節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)，這時(shí)就需要建立一個(gè)新的根節(jié)點(diǎn)。B-樹(shù)的插入可能導(dǎo)致B-樹(shù)朝著根的方向生長(zhǎng)。

例如，若想在如圖1-16所示的一個(gè)6階B-樹(shù)中插入關(guān)鍵字“33”，因?yàn)樵谧钣疫叺墓?jié)點(diǎn)中關(guān)鍵字的個(gè)數(shù)已經(jīng)達(dá)到5個(gè)，所以不能將“33”直接插入，而要把這個(gè)節(jié)點(diǎn)分裂為兩個(gè)，并把中間的一個(gè)關(guān)鍵字“36”拿出來(lái)插到節(jié)點(diǎn)的父節(jié)點(diǎn)里。1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)2．

B-樹(shù)

圖1-16一個(gè)6階B-樹(shù)圖1-17插入關(guān)鍵字“36”后的B-樹(shù)1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)2．

B-樹(shù)

4）B-樹(shù)的刪除B-樹(shù)的刪除分為以下兩種情況。（1）B-樹(shù)的刪除與插入類似，但會(huì)稍微復(fù)雜些。如果刪除的關(guān)鍵字不在葉節(jié)點(diǎn)層，就需要先把此關(guān)鍵字與它在B-樹(shù)里的后繼節(jié)點(diǎn)對(duì)換位置，然后再刪除該關(guān)鍵字。（2）如果刪除的關(guān)鍵字在葉節(jié)點(diǎn)層，則把它從它所在的節(jié)點(diǎn)里去掉，這可能導(dǎo)致此節(jié)點(diǎn)所包含的關(guān)鍵字的個(gè)數(shù)小于m/2-1。這種情況下，考察該節(jié)點(diǎn)的左或右兄弟節(jié)點(diǎn)，從兄弟節(jié)點(diǎn)移若干個(gè)關(guān)鍵字到該節(jié)點(diǎn)中來(lái)，使兩個(gè)節(jié)點(diǎn)所含關(guān)鍵字的個(gè)數(shù)基本相同。只有在兄弟節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)剛好等于m/2-1時(shí)，這個(gè)移動(dòng)才能進(jìn)行。這種情況下，要將刪除關(guān)鍵字的節(jié)點(diǎn)、其兄弟節(jié)點(diǎn)及其父節(jié)點(diǎn)中的一個(gè)關(guān)鍵字合并為一個(gè)節(jié)點(diǎn)。1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)2．

B-樹(shù)

4）B-樹(shù)的刪除

例如，要在如圖1-18所示的3階B-樹(shù)中刪除關(guān)鍵字“46”，刪除后該節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)為“0”，低于最低限制“1”，而它的左兄弟節(jié)點(diǎn)和右兄弟節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)都為最低限制“1”，所以只能將刪除關(guān)鍵字的節(jié)點(diǎn)、其兄弟節(jié)點(diǎn)及其父節(jié)點(diǎn)中的一個(gè)關(guān)鍵字合并為一個(gè)節(jié)點(diǎn)。

將關(guān)鍵字“46”刪除后，該B-樹(shù)如圖1-19所示。

圖1-18一個(gè)3階B-樹(shù)圖1-19刪除關(guān)鍵字“46”后的B-樹(shù)1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)3．B+樹(shù)

1）B+樹(shù)的定義B+樹(shù)是B-樹(shù)的一種變體。B+樹(shù)與B-樹(shù)的差異有以下幾點(diǎn)。

（1）在B-樹(shù)中，每個(gè)節(jié)點(diǎn)含有n個(gè)關(guān)鍵字和n+1棵子樹(shù)。在B+樹(shù)中，每個(gè)節(jié)點(diǎn)含有n個(gè)關(guān)鍵字和n棵子數(shù)，即每個(gè)關(guān)鍵字對(duì)應(yīng)一棵子樹(shù)。

（2）在B-樹(shù)中，每個(gè)節(jié)點(diǎn)（除根節(jié)點(diǎn)外）中關(guān)鍵字個(gè)數(shù)n的取值范圍是m/2-1≤n≤

m-1。而在B+樹(shù)中，每個(gè)節(jié)點(diǎn)（除根節(jié)點(diǎn)外）中關(guān)鍵字個(gè)數(shù)n的取值范圍是m/2≤n≤m。

（3）在B+樹(shù)中，所有葉節(jié)點(diǎn)包含了全部關(guān)鍵字及指向?qū)?yīng)記錄的指針，且所有葉節(jié)點(diǎn)按關(guān)鍵字從小到大的順序依次連接。

（4）在B+樹(shù)中，所有非葉節(jié)點(diǎn)僅起到索引的作用，即在節(jié)點(diǎn)中的每個(gè)索引項(xiàng)只含有對(duì)應(yīng)子樹(shù)的最大關(guān)鍵字和指向該子樹(shù)的指針，不含有該關(guān)鍵字對(duì)應(yīng)記錄的存儲(chǔ)地址。1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)3．B+樹(shù)

1）B+樹(shù)的定義

例如，如圖1-20所示的一棵3階B+樹(shù)，其中葉節(jié)點(diǎn)的每個(gè)關(guān)鍵字下的指針指向?qū)?yīng)記錄的存儲(chǔ)位置。通常在B+樹(shù)上有兩個(gè)頭指針：一個(gè)指向根節(jié)點(diǎn)，用于從根節(jié)點(diǎn)起對(duì)樹(shù)進(jìn)行查找、插入、刪除等操作；另一個(gè)指向關(guān)鍵字最小的葉節(jié)點(diǎn)，用于從最小的關(guān)鍵字起順序查找和處理在每個(gè)葉節(jié)點(diǎn)中的關(guān)鍵字和記錄。

由于B-樹(shù)只適合隨機(jī)檢索，B+樹(shù)同時(shí)支持隨機(jī)檢索和順序檢索，所以在實(shí)際中，B+樹(shù)應(yīng)用比較多，NTFS就是使用B+樹(shù)進(jìn)行動(dòng)態(tài)索引的。圖1-203階B+樹(shù)1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)3．B+樹(shù)

2）B+樹(shù)的查找B+樹(shù)的查找與B-樹(shù)的查找類似，但也存在不同之處。由于與記錄有關(guān)的信息都存放在葉節(jié)點(diǎn)中，在查找時(shí)若在上層已找到待查找的關(guān)鍵字，則查找不會(huì)停止，而會(huì)繼續(xù)沿指針向下一直查找到葉節(jié)點(diǎn)層的關(guān)鍵字。另外，B+樹(shù)的所有葉節(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，可以按照關(guān)鍵字排序的次序遍歷全部記錄。將這兩種方式結(jié)合起來(lái)，便使B+樹(shù)非常適合范圍檢索。3）B+樹(shù)的插入B+樹(shù)的插入與B-樹(shù)的插入類似，不同之處在于B+樹(shù)是在葉節(jié)點(diǎn)上進(jìn)行插入的。如果在葉節(jié)點(diǎn)中關(guān)鍵字的數(shù)量超過(guò)m個(gè)，該葉節(jié)點(diǎn)就必須分裂成關(guān)鍵字?jǐn)?shù)量大致相同的兩個(gè)節(jié)點(diǎn)，并保證在上層節(jié)點(diǎn)中有這兩個(gè)節(jié)點(diǎn)的最大關(guān)鍵字。1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)3．B+樹(shù)

4）B+樹(shù)的刪除

當(dāng)B+樹(shù)中的關(guān)鍵字在葉節(jié)點(diǎn)層被刪除后，其在上層的副本可以保留，作為一個(gè)“分解關(guān)鍵字”的存在。如果因?yàn)閯h除操作而造成在節(jié)點(diǎn)中關(guān)鍵字的數(shù)量小于m/2-1個(gè)，其處理過(guò)程便與B-樹(shù)的刪除操作一樣。1.3.4B樹(shù)、B-樹(shù)、B+樹(shù)和B*樹(shù)4．B*樹(shù)

B*樹(shù)是B+樹(shù)的變體，即在B+樹(shù)的非根節(jié)點(diǎn)和非葉節(jié)點(diǎn)中增加了指向兄弟的指針。B*樹(shù)的非葉節(jié)點(diǎn)關(guān)鍵字的數(shù)量至少為2m/3個(gè)，而B(niǎo)+樹(shù)的則是m/2個(gè)。B+樹(shù)的分裂方法：當(dāng)一個(gè)節(jié)點(diǎn)滿時(shí)，分配一個(gè)新的節(jié)點(diǎn)，并將原節(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新節(jié)點(diǎn)中，最后在父節(jié)點(diǎn)中增加新節(jié)點(diǎn)的指針。B+樹(shù)的分裂只影響原節(jié)點(diǎn)和父節(jié)點(diǎn)，不會(huì)影響兄弟節(jié)點(diǎn)，所以它不需要指向兄弟的指針。B*樹(shù)的分裂方法：當(dāng)一個(gè)節(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟節(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移動(dòng)到該兄弟節(jié)點(diǎn)中，再在原節(jié)點(diǎn)處插入關(guān)鍵字，最后修