來,什麼叫做Away Search Tree呢? Away Search Tree它有一個很重要的用途什麼用途? 它主要是用在外部搜尋上那我待會會跟各位解釋什麼叫外部搜尋不過我們先稍微介紹一下我們之前在談過的一些搜尋技巧來說它都是屬於內部搜尋比如說像我們在那個樹狀結構裡面曾經跟各位提到過二元搜尋數還記不記得我們之前是不是跟各位提到所謂的二元搜尋數Binary SearchTree二元搜尋數就是一種標準的內部搜尋方法還有就是我們待遇更貴介紹的另外一個叫做AVL TreeAVL Tree它也是一個很標準的內部搜尋方法到底什麼叫做內部搜尋呢內部搜尋主要意思在底下你們看一下所謂的內部搜尋的技巧是你現在搜尋的資料量是比較少少到就是說當你要對這堆資料去做資料的搜尋時這些資料可以一口氣往記憶體面擺如果說你今天你的搜尋資料量是比較少可以一次全部置於Memory的情況之下你所做的這種搜尋工作就是屬於內部搜尋法OK所以說像我剛剛講的什麼二元搜尋數也好或是AVLT也好基本上他們都是屬於這種內部搜尋也就是說我要對這些資料去做資料的搜尋時你所有資料要一口氣先往記憶體面擺你要是資料量太大,沒有辦法一口氣擺完的話Python這兩個演算法就會破功它就沒辦法去做資料的搜尋了好,所以說今天反過來講如果說你 的資料量實在很大的情況之下大到你沒有辦法一口氣把所有資料全部往建議裡面擺的時候這個時候你所要用的搜尋技巧是什麼呢?
就是屬於外部搜尋的技巧來,我們來看一下外部搜尋的技巧是什麼當你今天資料量很大的情況之下無法一致全部置於Memory當中這個時候我們需要借助輔助儲存體來進行分段的搜尋工作這樣的一個搜尋工作就是屬於外部搜尋而這邊我們經常會借助到的輔助儲存體一定都是硬碟硬碟最大顆嘛 又便宜對不對所以說通常來講我們在進行外部搜尋的時候我們會借助到的一個東西就是硬碟而且我們在談外部演算法的搜尋工作的時候他們以演算法的設計來講最大的運作瓶頸最大的那種效能執行的瓶頸也是在於這個硬碟我會教各位為什麼我會告訴各位為什麼OK好所以現在大家知道什麼叫做外部搜尋了對不對所以說現在目前我們的M-way search tree來說它主要就是用在所謂的外部搜尋這樣的一個技巧也就是說現在你面對的資料量是非常龐大龐大到你沒有辦法一口氣將所有資料全部擺到記憶體裡面去你必須要做分段搜尋時你就要採用這種M-way search tree去做那這個時候你用Binary search tree或是Avial tree都沒有辦法去執行它都沒有辦法執行來那我們來看一下那N位攝取區它是一個什麼東西呢? N位攝取區它這一顆數來講它的degree它的tree degree來說是N它會等於N那N是什麼呢? 那N的話它是要大於2也就是說以這一顆數來說它的分支度它是絕對是大於2的情況是大於2的情況來那為什麼它不是二元素的結構呢? 因為按照我們之前在第五章跟各位談有關於樹狀結構來說如果你這一棵樹想要利用所謂的鏈結串流的方式存放到電腦系統裡面去的話我們用二元素的方式它的link它的空間會比較省嘛對不對至少你浪費的那種link空間也不會那麼多可是為什麼我們這邊又反其道而行我們的這個amazer tree它的tree的degree是大於2呢其實在這邊來講的話呢我們是為了要壓縮樹的高度我們是為了要壓縮樹的高度我們解釋底下給各位看因為啊外部搜尋它的資料量非常龐大如果你還是以二元素的結構去存放這些資料的話則你這棵樹的高度會很高感覺出來樹光會很高喔所以說這個時候如果你要做資料搜尋的時候你必須要從樹的根節點開始一個一個找一個一個往下找這樣的話你的資料搜尋的時間會非常非常的耗時所以說這邊為什麼我們不採用二元素的這種架構原因在這裡當然啦這是原因之一這是原因之一它的原因之二的話呢基本上它的主要理由還是我們要把那個樹的高度把它壓縮但是呢樹的高度壓縮來說其實最主要我們是要節省一個東西什麼東西呢? Disc IO這個動作我稍微給各位Disc IO我們要節省Disc IO這個動作為什麼呢?
其實Disc IO這個動作它非常非常的耗時非常非常的耗時難你們計算機概論應該還記得啦你們在計算機概論裡面應該有跟各位提到有關於Disk I.O來講Disk 硬碟這個東西它是屬於機械式的運作對不對在硬碟裡面的話我們是將資料放在所謂的硬盤上面就是說那個磁碟盤上面那這個磁碟盤我們今天是要靠讀寫頭硬碟的讀寫頭去將我們某一個磁軌上的資料把它讀取出來但是我們要做資料讀取的時候我們要先去做磁碟盤的旋轉動作這個旋轉動作它本身是一個機械動作好,當你今天要把你要讀取那個資料所在的磁區把它轉到那個讀寫頭的下方之後這個讀寫頭才會以機械的運作方式去把那些資料放在那裡Touchdown 我們那個磁碟盤它所在那個磁區上當然它不是真正的接觸啦它還是有點點空隙還是有點點空隙OK那只是說呢我要跟各位強調的是因為我們的Disk它本身的運作它是機械式運作所以它的運作輸入非常的慢那當你今天在從事外部搜尋的時候如果你這個硬碟的輸入輸出資料的輸入輸出動作一大的情況之下那你整個外部搜尋的效率就會變得非常非常的低落來 我們這邊舉一個簡單的圖示給各位看現在左手邊像罐頭的東西它就是硬碟來 我們中間這個長條的東西它是主記憶體右邊這個橢圓形是CPU根據你們計算機概論裡面學的那個計算機的五大架構應該看得出來來這邊的話如果說今天我們要從事外部搜尋的時候你可以想像一件事情因為現在我們的資料量非常龐大那龐大到就是說我們沒有辦法將這些要搜尋的資料一口氣往記憶體裡面搬對不對所以說我們有一些資料逼不得已要先擺放到硬碟裡面去做等待那你想想看喔如果這個時候我在做資料的搜尋過程當中如果說硬碟IO的次數過多的情況之下它是不是會將整個搜尋的效率把它整個拉低為什麼會拉低呢因為我們的CPU跟我們的主記憶體它本身是屬於電子式的運作它的速度非常快它根本沒有任何所謂的機械的運作在裡面所以它的速度非常非常的快可是我們的硬碟呢它本身是機械式運作機械式運作來說它的速度就是比電子式運作的設備來得慢很多你可以這樣想像啦如果說我們的主記憶體跟CPU它們的運作效率它們是兔子的情況之下你可以把這個Disk當成是蝸牛它連烏龜都排不上懂意思嗎它連烏龜都排不上它就是蝸牛OK所以它的運作的速度會非常非常的慢那你這樣想的話呢如果說我們今天整個這種搜尋的工作啊都擺在硬碟上面而且我會從事好多次的IO運作的話你就會發現到你這個整個工作的效率就會變得很低落我講到這邊你們可能還是沒有辦法體會我先舉一個實際的例子給你們聽比如說像各位你們在打GAME你們在打GAME的時候呢像各位你們現在都打那種戰略式遊戲對不對那每一個主角可能武器一大堆對不對那你們這個主角他可能在打怪的過程當中他可能一直換武器有啦吼打CS也是這樣子啊對不對會一直在那邊換武器嘛對 換了你很煩啊像我現在快速鍵都一直換不過大家來 那你想想看喔現在我假設一件事情假設這些武器全部都是擺在硬碟裡面也就是說呢當今天主角這個武器他不想用的時候他不是往記憶體裡面丟先做暫存的動作而是直接往硬碟裡面擺那你想想看喔當今天你這個主角他想要換武器的時候當你今天把這個換武器的快速鍵一按下去的時候你會發覺你的電腦系統停了一下為什麼呢? 因為這個時候你的電腦系統正在硬碟裡面在吵說他剛剛挑的武器是哪一根他在硬碟裡面在那邊翻你的武器目錶開始在那邊找看你要選的武器到底是哪一支好,當你今天從硬碟裡面把武器挑出來之後把它放回到系統裡面讓它去做執行的時候這個時候你可能隔了一兩秒才發現到怎麼這個主角開始繼續往下跑下去了OK好 當你今天這個主角在打怪打到一半你又想換武器的時候呢這個時候當你今天把那個換武器的快速鍵又按下去的時候你又發現到系統又停了一下幹什麼呢把原本的武器放回硬碟然後這個時候再從硬碟面把你接下來要選的武器再把它撈出來那這樣子你想想看當你今天這個DiscIO這樣一直跑來跑去的時候這個Gang將打下來流不流暢不流暢啊 你會打得很幹啊 對不對所以說 基本上來講啊我們為什麼要強調就是說我為什麼剛剛要以武器的替換這樣來講原因就是當你今天把武器擺到硬碟裡面去挑下一個武器出來的時候它本身就是一種搜尋動作而這個搜尋動作來說 牽扯到的是硬碟的IO牽扯到的是硬碟的IO所以你們可以想像一件事情如果你今天你要找取的資料全部都要透過硬碟IO這樣一直跑來跑去的話那這樣子,當你今天Disk IO的次數一大那此時你這個搜尋動作它的效率一定低落OK? 講了這麼多應該可以吧? 感覺出來那個低落的那種feel了嗎? OK?
好! 假設可以了啦繼續往下說了所以說基本上我們把一棵樹它的底規拉大除了要讓一棵樹它的高度能夠壓縮以外其實最主要還有另外一個用途就是我希望它的Disk I.O.的次數能夠降低它的Disk I.O.的次數能夠降低降低的話這樣子我們在做外部搜尋的時候我的效率才會提升知道了好那我們就要繼續往下了所以說我們今天使用On-Way Search Tree來講的話主要的目的就是我們要想盡辦法去提升外部搜尋的效益你要提升外部搜尋的效益的話主要的一個做法就是你要想辦法去降低Disk IO的次數你不降低這個什麼都不要談可以嗎? 我們要想辦法去降低Disk IO的次數你今天要降低Disk IO的次數的話你要想辦法去降低你這個Search Tree它的高度也就是說你要想辦法把這根原本是很高的一棵樹把它扁平化好,那你要把這個search tree它的高度做扁平化降低它的高度這個動作來說的話呢這個時候你要去增大這一棵樹它的degree也就是說呢,你一個節點原本它只能允許分支度為2那如果這樣子的話呢,你可以把這個每一個節點它的分支度變大一點變成分支度為3,分支度為4這樣子的話呢,基本上我們整棵樹它的高度就會變得比較扁平OK,那這樣子做的話基本上就可以提升我們整個在做外部搜尋值的一個效益那可能會有人問我一件事情老師我們之前在談二元搜尋數的時候是不是有講過就是當你今天如果你一個二元搜尋數如果是夠平衡的情況之下其實它高度也不會太高可是問題是啊當你今天資料量非常龐大的情況之下你這個平衡的二元搜尋數它的高度還是很可觀還是很可觀所以說基本上我們在降低一顆數的高度來說我們讓一顆二元素平衡它只是手段之一但是這種手段來說我們用到外部搜尋來講的話它並沒有辦法將整個二元素的高度真的做到最大的壓縮沒有辦法那你真正有辦法就是你把每一個節點它的degree把它拉大變成分子度為3分子度為4或分子度為5這樣子一個degree才有辦法真正的將一顆數它的高度把它壓縮成比較扁的一顆數那怎麼壓? 待會兒會教各位來,那這邊的話呢,我們就來看一個實例比如說現在我有一堆資料這堆資料裡面,我想要去找尋15這個β來,那我現在左手邊這個範例來說的話呢我現在就是採用外部搜尋所以說我的資料呢,都是往那個硬碟裡面擺來,那可是呢,這個時候我先不採用所謂的unweighted tree我先用之前教過各位的那個二元搜尋數好了先用二元搜尋數來跟各位談這件事情你看喔所以假設我有非常龐大的資料那這個非常龐大的資料的話呢我今天把它建構成所謂的二元搜尋數這二元搜尋數的話呢基本上來講每一個節點它的分支度是為2嘛對不對所以說它整個建下來來講其實它的高度還蠻高的因為我資料量很大OK這樣可以嗎好那這邊的話呢你看喔還記不記得你在計算機概論裡面學到的一個東西我們在硬碟裡面的話呢硬碟的儲存單位是什麼?
是不是一個block一個block就是一個區塊嘛對不對那所以說呢以我這邊來講的話呢這每一個方框框它就是一個block就是一個區塊那這區塊的話呢可能256byte或多少隨便啦那這看你怎麼去規劃這個持續大小啦好那這先不管那各位看一下喔如果說我現在想要對這個二元搜尋數在硬碟裡面的這個二元搜尋數我要去找尋15這筆資料的話我一開始是不是先從這個二元搜尋數的樹根開始找起對啦吼好 所以說現在一開始的時候呢我要將這個樹根的資料把它輸出到我們的系統裡面去也就是說我要從硬碟裡面把26樹根的資料把它抓出來來 抓出來之前我先跟各位講一下我的紅色箭頭代表說我的資料是從Disk把它拿出來那藍色箭頭的話呢我是把資料把它往我們Disk裡面丟也就是說這個藍色跟紅色的箭頭代表說你的資料的輸入輸出Disk IO那個動作來,那你們看一下喔因為現在目前26這個數根它的資料是擺在硬碟裡面所以說我要先把它調到我們的系統裡面去先把它做Disk OUT的動作把這26往我們的系統裡面擺然後這時候我們的CPU就去判斷說26是不是我要的資料現在一比顯然不是嘛,對不對因為我們現在要找的資料是多少? 15啊那我現在撈出來的資料是多少? 26啊它不是我们要的资料嘛对不对好最终的一笔之下我发现到26不是我要的资料那请问各位15比26大還是小? 小嘛對不對好,所以說這個我就知道那我現在接下來要找的位置應該是在26這個數跟它的左分支的地方有沒有,所以說現在接下來我就要把26這個資料從我們的系統把它擺回到硬碟裡面去,把它擺回去OK,那擺回去之後呢接下來我要把26這個根節點它的左分支的資料把它調出來也就是我們把這個10給撈出來,可以嗎把它繞到我們的記憶體裡面去,讓CPU去比對是不是我們要的資料就一筆之下發育到15跟10不一樣嘛對不對代表說現在這個10也不是我們想要找的data按照二元搜尋數的概念來說請問一下我們撈出來的這個資料是10可是我們真的要找的資料是1515比10大所以說我現在接下來要找的那種分支應該是10這個節點的左分支還是右分支右分支嘛對不對好所以說你看喔10不是我們要的資料,我們就把它放回到硬碟裡面去這時候我們看一下10這個節點,我們有左分支跟右分支但是呢,因為現在15這個資料它是比10來的大所以說接下來我是要往右分支這邊找那右分支找的話呢,這個時候呢是不是把15給撈出來了來,那這時候15撈出來之後呢,再跟我們要找的這個資料去做比大小的動作一比之下,欸比到了嘛,對不對好,那所以說呢,這個時候我們才知道我們15真的被我們找出來了從硬碟裡面這樣可以嗎?
那請問各位啊我現在找15這筆Data來說我以這個硬碟裡面的二元收訊數來說我做了幾次IO動作其實我總共做了三次有沒有拍到? 我總共做了三次的IO動作這是個IO這一次嘛這一次嘛那這一次雖然它是半次啦不過也給它算一次啦好不好我做了三次硬碟IOOK所以你想想看喔你這一顆二元數的高度會影響到你的DiskIO的次數可以嗎你存放在硬碟裡面這個二元數的高度會影響到直接影響到你DiskIO的次數所以說呢如果你純粹利用二元搜尋數的方式將很大量的資料去建構出二元搜尋數的話你在做這個DiskIO在做資料搜尋的時候你這個DiskIO的次數會非常非常的可觀那是很可怕的一件事情好 那我現在想辦法去壓縮這棵樹的高度怎麼壓呢? 我現在把這棵樹裡面的每一個節點它的分支度拉大我不再限制說每一個節點只能分支度為2你可以分支度為3、分支度為4我把它拉大拉大來看其實你會得到旁邊這棵樹你有沒有發現到旁邊這棵樹它的高度就少很多看到了嗎? 有啦齁你看喔,我們以樹根這個節點來說樹根的這個節點的話呢它的分支度是4因為它的Bx有4根嘛對不對?
好那底下的話呢,23這個block來講23這個block它的分支度為3因為它有3個分支那8這個block來講的話呢,它的分支度為2然後呢,15、16這個節點它的分支度是3因為它有3個分支30、40、50這個block來講的話呢,它的分支度為4所以說你們看一下喔當你今天分支度為4的這個節點來說它裡面一定會有三筆資料當你今天分支度為3的這個節點就像我們左下角這個23當你今天分支度為3的這個節點來說裡面擺放的資料量一定是2可以嗎? 為什麼呢? 你看喔當我今天一個節點它的資料量是3的話比如說它有3筆資料對不對3個資料的話呢每一個資料我都可以去長一些分支比如說我從這邊長一個這邊他們共用一個分支共用一個分支它是 怎麼長?
我們後面告訴各位所以說基本上當你今天一個block裡面有三筆資料的時候資料跟資料之間他們可以共用一個分支但是在你今天最左手邊的資料它本身會多一個左分支出來最右手邊的資料它本身會多一個右分支出來這樣子看得出來嗎? 為什麼會這樣? 我們後面會談它的節點結構你們先暫時把它記起來這樣就可以了好,所以說各位你們看一下我現在把每一個節點把它放大來看他們的分支度變成這麼大OK來這樣的話我們在做資料的搜尋的時候它就很快了來我們怎麼看呢你看我一樣是先從樹根開始找起可是樹根的話我這個樹根裡面資料有幾筆有三筆所以說我是一次將這個樹根裡面的所有資料把它撈出來到我們系統裡面去做搜尋我們一比較之後我們發現到15這筆資料我們這邊撈出來的資料是50、20都沒有對不對那都沒有的情況之下的話呢我們接下來就要去找那個其他的節點但是我找其他的節點的時候呢我發現到一件事情我要找的這個資料15介於10跟20之間有沒有看到我要找的這筆資料15是介於10跟20這兩個資料中間嘛對不對所以說這個時候呢我要接下來去找其他的節點的時候呢我就是從10跟20之間他們的這個比特下去找這個分支下去找好 所以說你看喔現在50、20都沒有我們要的資料所以說呢我們就把50、20把它再放回到硬碟裡面去接下來的話,因為我們知道我們要找的資料是介於10跟20之間所以說我們接下來要找的那個節點是藉由10跟20之間的這個分支所連接到的下一個頂點把它撈出來去看所以說你們看一下,我們現在找出來的結果是這樣子我們這時候撈出來就是15跟16撈出來15跟16之後我們再去跟15這個資料做比較發覺到你撈出來這一堆資料裡面真的有我想要的資料好所以說你們看一下,我在這一次的改進動作裡面我的DiskIO做了幾次?
這邊算一次,這邊也給它算一次幾次? 兩次啊! 我做了兩次耶!
所以你有沒有發生到一件事情如果我說我把同樣的一堆資料但是我所存放的這個樹狀結構它的degree把它放大的話呢基本上它的高度會變得比較扁而且這個時候我在做所謂的IO的時候DiskIO的時候,我的次數會變得比較少這樣子可以嗎? OK? 所以說在這邊我們就可以透過把tree的degree把它放大這樣子我們可以去壓縮我們的樹的高度而且同時我們在做disk IO這個動作來說次數也會變得比較低所以說我們右手邊這個改進的樹上結構它就是屬於emphasis tree那在emphasis tree來說的話基本上我們先從這個地方來跟各位看我們來看幾個特徵這個特徵我們待會一樣會談來首先還是一樣,第一個特徵是什麼呢? 如果你這個節點,它的分支度是4的情況之下代表說你這個節點裡面可以擺3筆資料如果你的節點它的分支度是3的情況之下代表說你這個節點裡面可以擺2筆資料如果說你這個節點它的分支度是2的這種情況之下代表說你裡面所能夠擺放的資料只能擺1筆OK? 好,所以我把這個特徵寫下來給各位大家抄一下吧如果你這個MASRT它的degree等於4則每一個節點最多可以放3個data當然啦當然是要看你每一顆節點它的degree是多少如果你這個節點它的degree是等於3的情況之下所以你這個節點它最多可以存放2個data如果你這個degree是3的情況之下那你這個節點裡面可以存放的資料是2兩個資料這個data的話,在我們的N-way search tree來說的話這個data我們可以給它稱之為key可以給它稱之為key那底下基本上是延伸如果你的degree是m的情況之下則每個節點最多可以存放m-1個data可以存放m-1個data這邊請各位稍微抄一下,這個關係有點重要所以說你們可以比照底下這個圖裡面每個節點所以說你們就知道一件事情我這棵樹如果把它每一個節點它的degree把它放大的話那這樣子我可以讓整棵樹的高度把它壓縮而且呢我這樣壓縮一個好處是我在搜尋資料的過程當中速度除了快以外我的那個disk IO的次數也會變得比較少這是我們想要的這個效果也就是說我們可以讓外部搜尋的效率可以把它提升那這個時候就會有人問我一個問題啦欸老師啊按照你這個定義來講的話那如果說我今天把這棵樹它的degree也就是把它那個m把它放到無窮大也就是說我所有資料全部把它擺放到一個節點裡面去那這樣子我這個MMA Search Tree它的高度是最低的啊對不對 因為我只有一層嘛那如果按照這樣講的話呢 你的Disk IO次數不是最低嗎我可不可以這樣擺請問同學 我可以這樣擺嗎不行嘛 對不對 我現在問就一定是不行啦那為什麼不行不行的原因在底下喔 你們看一下因為啊 當你如果說你這個M1設計區它的M它的degrees是無窮大的情況之下沒有錯啦你這整棵樹的高度是只有一層而且按照字面意思來說你在做DISIO的時候你只有一次這沒有錯問題是現在就是因為你的資料量太過龐大你沒有辦法一口氣將你所有要搜尋的資料往記憶體裡面擺你才要做分批搜尋嘛對不對那如果說你今天可以將你所有要搜尋的資料往一個節點裡面塞而且你這個節點裡面的資料你翻一次到記憶體裡面你就可以一次把它搬完的話其實你也可以不用Mrater Tree這個技巧了因為這個時候的話呢你只要按照我們之前教給各位的內部搜尋的所有這種skill你就可以去處理掉你的搜尋問題了OK懂我意思嗎所以說各位看一下如果說你的M為無窮大的情況之下雖然你這一顆數高度只有一層但是因為你的資料太過龐大無法一次放到Memory當中所以說呢你這樣子把那個這個Degree放到無窮大的這個目的基本上也是破功啦為什麼呢?
你資料量太大了嘛OK所以說呢你這個DegreeM來說的話呢我們會以Memory的Size做一個界限我們不會讓你無止無盡的這樣子把你這個Degree放大啦不可能啦OK好所以說各位看一下如果你所有資料可以一次全部放到記憶體裡面去的話呢那這個時候你所面對到的搜尋的這種議題就是屬於內部搜尋你這個時候就不用外部搜尋的技巧了啦按照我們之前教給各位的那個二元搜尋數或是我們那個AVLTree基本上就可以了就夠了也就不用外部搜尋的技術也就是我們這邊要教的M-way search tree就不用了所以說呢你這個時候只要用Internal search的議題去做相關的處理就可以了你不需要用到外部搜尋的技術這樣子可以嗎所以說你這個M-way search tree它的degree不是讓你無窮無盡的放大這樣子可以嗎可以喔那我們繼續往下講了拜拜我們現在正式來談一下MA3它的定義到底是什麼來我們來看一看MA3來說它是一個所有節點的分支度小於等於m的一顆數那這個數的話基本上它可以是空數如果這顆數不為空的情況之下則有底下這些性質它總共有四大性質我們一個一個來看首先第一個性質是先跟各位介紹一下MA3它的節點來看一下喔我們先來看一下M-Message的節點結構是長什麼樣子呢基本上它的節點結構是長像這樣子啦NA0 然後K1A1 K2 A2 然後點點點一直到KN AN那這些是什麼東西呢 可能各位看不太懂啦來 我們分別幫各位做解釋首先第一個在我這個節點結構裡面假設我每一個節點裡面資料量是N的情況之下那這樣子我們來看一下 這個見值個數也就是我們那個資料量的個數來說 這個N一定是小於等於m-1這個東西是什麼呢? 這個東西是我剛剛抄給各位那兩段話還記不記得如果你有一個節點它的分支度為4的情況之下代表說這個節點裡面可以擺放幾筆資料? 3筆那如果說你這個節點它的分支度是m的情況之下代表說你這個節點裡面可以存放的資料量是多少?
m-1沒錯,就是這個可以嗎? 就是它所以說我剛剛前面為什麼要抄給各位就是為了這一段話好所以說基本上來講當你今天有一個節點這個節點它的分支度為M的情況之下那這個節點來說裡面所能夠存放的資料量也就是它的漸值的個數會小於等於M-1個它的資料量最大是到M-1OK好那我這邊的什麼K1K2K3來自於點點點到KN來說這些K是什麼呢就是你的資料就是我剛剛講的這些漸值以我們這邊來講的話這個漸值個數是N嘛所以說我這個Ki就會有N個我們的資料會有N個那這個A是什麼東西呢? A0A1 A2A3乃至於...叫An這些A是什麼東西呢?
Ai來說它代表是一個指標指向存放大小介於Ki與Ki加1之間的資料之節點所在所以說我們今天把這樣的一個節點結構來說我們把它翻倒幾下來看這邊的話呢,它就是一個我們Message Tree的其中一個節點它的節點資料會有這些來,首先第一個這個地方是存什麼東西呢? 是存放說你這個節點裡面總共有幾筆資料也就是幾個key啦你有幾筆資料那現在我們這邊是有N筆資料嘛所以說你們看一下喔因為我現在這個節點裡面可以擺放N筆資料所以說我的K是從1到N有沒有看到? 我會有N筆資料好,來那這邊的話呢 接下來主要來看它的分支度也就是摄像頭那個箭頭那個指標的部分這個箭頭的話代表說你這個節點的分支度那這個分支度的話呢 是從A0A1 A2A3一直點點點到ANOK那這邊是一個節點來 那這時候我們來看 直接舉一個範例給你們看這邊就是一個很標準的MV3 有畫到沒有好 那你們看一下喔這個節點裡面的話呢 其實我畫得比較詳細一點的話呢這裡面的所有的節點都少了一個欄位就是N那個欄位如果說你們要的話我可以補上但是原則上是不需要補啦來 這邊的話呢因為我現在跟節點來說裡面存放的是三筆資料對不對所以我的N是3那我下面這個節點來說的話呢裡面存放的兩筆資料所以它的N是2道理來說我們的節點結構完整的畫法應該是長這樣子但是呢基本上我們在做後續的運作的時候我們不要這麼麻煩所以說有關於N這個地方我們直接在我們後面在談那個紙上的運作時直接把那個N拿掉因為這是在實作上來講才會使用到的一個欄位好那這邊我們來看這個你們就補上去來然後我這邊把它塗掉,因為我們在實作上來講可以先不用看它來,我們來看一下,以根節點來說根節點它的分支度,也就是它設出去的邊有四格對不對所以說以這個節點來說,裡面可以存放的資料量是3可以嗎?
M-1嘛,還記得啦那這邊每一個節點都是一樣所以說呢,我們在談所謂的N-way search tree它的節點結構來說你們可以把它稍微做個對應,就可以看得懂了來然後接下來我們來看第二個特性第二個特性是什麼呢? 每一個節點裡面的件值也就是我們講的那個資料啦我們都是由小到大排序的這是規定節點當中的每一筆資料都是由小到大排序好的所以說呢以這個根節點來看5、10、20它是排序好的那以另外一個節點來看2、3排序好的以另外一個節點來看30、40、50有沒有看到全部都是由小到大排序好的這樣可以嗎? 第二個特性應該可以啦這是有關於第二個特性的部分節點當中的每一個資料都是由小到大排序好的第三個,env3它的指數來說一樣是env3所以說它是屬於遞回的概念這個env3它的底下的指數也是env3它是遞回的一個概念第四個的話,我先念過一遍它的概念有點複雜,但是直接講例子非常簡單什麼意思呢? 我們來看一下指數Ai內的資料均小於見值Ki加1指數An內的資料均大於見值Kn這段看不懂對不對? 直接舉例給你們看,各位看一下5這個資料按照我們上面那個節點資料結構來說它是屬於K1,對不對?
那我們現在這邊是不是A0按照上面的資料結構來看另外這個箭頭來說是不是A1A嗎? 來我們來看一看A0這個箭頭所指向的這個節點裡面的所有資料值是不是比上面這個K1來的小對不對那A1呢這個箭頭所指向的這個節點裡面的值是不是都比K1這個來的大對啦就是這樣子啊這一段話講的是這件事情啦好來我再隨便舉個點我們這邊這個的話呢 我們把它拉過來看假設它是KN假設它是KN這邊是KNKN也是啊KN的話呢 代表說我現在這邊射出去的這一條邊是AN 對不對KN這個值是20AN射出去的這個邊 它所指到的這個節點它裡面的資料是30 40 5030 40 50都比你這個KN這個指來的大嘛所以說是不是後面這一段話啊看得懂了,自己對一下就會了自己對一下就會了所以底下這個特性,只能是這件事情而已