<kbd id="afajh"><form id="afajh"></form></kbd>
<strong id="afajh"><dl id="afajh"></dl></strong>
    <del id="afajh"><form id="afajh"></form></del>
        1. <th id="afajh"><progress id="afajh"></progress></th>
          <b id="afajh"><abbr id="afajh"></abbr></b>
          <th id="afajh"><progress id="afajh"></progress></th>

          請問二叉樹等數(shù)據(jù)結(jié)構(gòu)的物理存儲結(jié)構(gòu)是怎樣的?

          共 5666字,需瀏覽 12分鐘

           ·

          2021-03-31 14:58

          走過路過不要錯過

          點擊藍字關(guān)注我們


          請問二叉樹等數(shù)據(jù)結(jié)構(gòu)的物理存儲結(jié)構(gòu)是怎樣的?

          好吧,咱們書上說了,一般兩種存儲方式: 1. 以完全二叉樹的形式用連續(xù)空間的數(shù)組存儲; 2. 以鏈表形式存儲,即各個數(shù)據(jù)之間保存了相關(guān)的數(shù)據(jù)的指針地址!
          如果回答就是這樣,那么我想大家也不費那神了,直接洗洗睡吧?咱們能不能深入點? 

          數(shù)組是好理解的,在內(nèi)存在磁盤都是一樣的,連續(xù)相鄰的空間,挨著存放到磁盤就可以了;好吧,就算你正確?那么鏈表呢?拿簡單的單鏈表來說,上一個節(jié)點保存下一個節(jié)點的指針?是如何保存的?我們能想到的,就是一個上一節(jié)點存儲了下一節(jié)點的絕對地址或者偏移地址,好像是這樣的!

          那么問題來了,這個下一節(jié)點地址到底是什么樣的呢?是相對地址還是絕對地址?這個地址是怎么算出來的?存儲在內(nèi)存上是肯定沒有問題的!但是如果存儲在磁盤上呢?如果這個地址是固定的,那么,如果換了硬盤(換了存儲介質(zhì)),是否就找不到該地址(因為每個設(shè)備的地址自然是不一樣的)?

          針對這個問題,很是困擾了我很久!也詢問過幾個身邊的小伙伴,也都說不知道。后來在一次面試中,一面試官剛好問我這問題,我把自己的見解說完后,說我確實不知道是怎么存儲的。最后我要求他給予答案,然后,他說,就是存儲的下一節(jié)點的地址(內(nèi)存地址),壓根不存在什么數(shù)據(jù)結(jié)構(gòu)存儲于磁盤這種說法,內(nèi)存中,是動態(tài)計算的值。如果存在內(nèi)存拷貝,那么,也會重新計算這些地址的,所以看起來相同的結(jié)構(gòu),在不同存儲工具上,會會表現(xiàn)出不同的地址空間。

          好吧,我將信將疑!被丟了n個鄙視的表情,然后被pass掉了。

          那么,到底內(nèi)存中的二叉樹怎么存儲在硬盤上的呢?

          其實硬盤上并沒有什么二叉樹的,硬盤只是充當(dāng)了一個存儲介質(zhì),只是提供你要讀的時候可以取而已,而真正的數(shù)據(jù)結(jié)構(gòu),則需要在用的時候再還原出原來的樹形結(jié)構(gòu)!

          下面以一個簡單的示例來展示磁盤上的數(shù)據(jù)結(jié)構(gòu)的存儲方式:

          public class BinTreeDiskSample {    private static int h = -1;    private static Node root;    static class Node implements Serializable {        private static final long serialVersionUID = -4780741633734920991L;        int data;        transient Node left;        transient Node right;        int lHeight = -1, rHeight = -1;        public Node(int data) {            this.data = data;        }        public Node setLeft(Node left) {            this.left = left;            return this;        }        public Node setRight(Node right) {            this.right = right;            return this;        }        public Node getLeft() {            return left;        }        public Node getRight() {            return right;        }        // 后續(xù)遍歷寫入,先序遍歷讀出        public int write(ObjectOutputStream out) throws IOException {            if (left != null) {                lHeight = left.write(out);            }            if (right != null) {                rHeight = right.write(out);            }            h++;            out.writeObject(this);            return h;        }        private void init(List<Node> list) {            if (lHeight != -1) {                left = list.get(lHeight);                left.init(list);            }            if (rHeight != -1) {                right = list.get(rHeight);                right.init(list);            }        }
          } public static void binTreePreOrderPrint(Node root) { System.out.print(root.data + " "); // visit root if(root.left != null) { binTreePreOrderPrint(root.left); } if(root.right != null) { binTreePreOrderPrint(root.right); } } // 先序遍歷讀出 public static void read(ObjectInputStream in) throws IOException, ClassNotFoundException { List<Node> list = new ArrayList<Node>(); Node n; Object obj; try { while ((obj = in.readObject()) != null) { n = (Node) obj; list.add(n); } } catch (Exception e) { // EOFException ...// e.printStackTrace(); } root = list.get(list.size() - 1); root.init(list); } public static void main(String args[]) throws FileNotFoundException, IOException, ClassNotFoundException { // 構(gòu)造一棵二叉樹 11 21 41 61 51 31 Node n6 = new Node(61); Node n4 = new Node(41).setLeft(n6); Node n5 = new Node(51); Node n2 = new Node(21).setLeft(n4).setRight(n5); Node n3 = new Node(31); Node n1 = new Node(11).setLeft(n2).setRight(n3); root = n1; System.out.println("output node: "); binTreePreOrderPrint(root); // 將數(shù)據(jù)寫稿磁盤 ObjectOutputStream out = new ObjectOutputStream(new FileOutputStream("btree.bin")); root.write(out); out.close();
          root = null; // 將數(shù)據(jù)從磁盤讀入,并進行數(shù)據(jù)結(jié)構(gòu)的重新構(gòu)建 ObjectInputStream in = new ObjectInputStream(new FileInputStream("btree.bin")); read(in); in.close(); System.out.println("\nread node: "); binTreePreOrderPrint(root); }
          }

          輸出:

           

          如上二叉樹的磁盤存儲,使用了java自帶的序列化工具,將節(jié)點寫入磁盤(注:這并不是一種好的實踐),然后在讀出的時候,按照寫稿時候的規(guī)則,進行重新構(gòu)建二叉樹即可。

           所以:

          存儲磁盤的數(shù)據(jù)結(jié)構(gòu),只是一種約定的方式,只是為了方便在重新恢復(fù)鏈表,二叉樹等等內(nèi)存結(jié)構(gòu)的算法而已。

          如:數(shù)據(jù)庫索引是存儲在磁盤上,當(dāng)表中的數(shù)據(jù)量比較大時,索引的大小也跟著增長,達到幾個G甚至更多。當(dāng)我們利用索引進行查詢的時候,不可能把索引全部加載到內(nèi)存中,只能逐一加載每個磁盤頁,這里的磁盤頁就對應(yīng)索引樹的節(jié)點。

          B+/-樹索引用使用很多的數(shù)據(jù)結(jié)構(gòu),下面做一點簡單介紹:

          一、B-Tree
            m階B-Tree滿足以下條件:

            1、每個節(jié)點最多擁有m個子樹

            2、根節(jié)點至少有2個子樹

            3、分支節(jié)點至少擁有m/2顆子樹(除根節(jié)點和葉子節(jié)點外都是分支節(jié)點)

            4、所有葉子節(jié)點都在同一層、每個節(jié)點最多可以有m-1個key,并且以升序排列

          二、B+Tree的定義
            B+Tree是B樹的變種,有著比B樹更高的查詢性能,來看下m階B+Tree特征:

            1、有m個子樹的節(jié)點包含有m個元素(B-Tree中是m-1)

            2、根節(jié)點和分支節(jié)點中不保存數(shù)據(jù),只用于索引,所有數(shù)據(jù)都保存在葉子節(jié)點中。

            3、所有分支節(jié)點和根節(jié)點都同時存在于子節(jié)點中,在子節(jié)點元素中是最大或者最小的元素。

            4、葉子節(jié)點會包含所有的關(guān)鍵字,以及指向數(shù)據(jù)記錄的指針,并且葉子節(jié)點本身是根據(jù)關(guān)鍵字的大小從小到大順序鏈接。

           

          下面讓我們來看看現(xiàn)代數(shù)據(jù)庫的磁盤存儲結(jié)構(gòu)吧:

          以下部分內(nèi)容摘自:https://blog.csdn.net/qq910894904/article/details/39312901

          我們都知道,數(shù)據(jù)庫通常使用B+樹作為索引,但是國內(nèi)很少有人提到數(shù)據(jù)庫使用的是HeapFile來管理記錄的存儲。國外的一些大學(xué)在“數(shù)據(jù)庫系統(tǒng)實現(xiàn)”這門課上通常會讓學(xué)生實現(xiàn)一個簡單的數(shù)據(jù)庫,因此有不少HeapFile的資料。

          基于Page的HeapFile
          采用鏈表形式的是HeapFile如下:

          Heap file和鏈表結(jié)構(gòu)類似的地方:

          支持增加(append)功能
          支持大規(guī)模順序掃描
          不支持隨機訪問

          這種方式的HeapFile在尋找具有合適空間的半空Page時需要遍歷多個頁,I/O開銷大。因此一般常用的是采用基于索引的HeaFile.在HeapFile中使用一部分空間來存儲Page作為索引,并記錄對應(yīng)Page的剩余量。如下:

          像上圖那樣,索引單獨存在一個page上。數(shù)據(jù)記錄存在其他page上,如果有多個索引的page,則可以表示為:


          下面是Heap file自有的一些特性:

          數(shù)據(jù)保存在二級存儲體(disk)中:Heapfile主要被設(shè)計用來高效存儲大數(shù)據(jù)量,數(shù)據(jù)量的大小只受存儲體容量限制;

          Heapfile可以跨越多個磁盤空間或機器:heapfile可以用大地址結(jié)構(gòu)去標(biāo)識多個磁盤,甚至于多個網(wǎng)絡(luò);

          數(shù)據(jù)被組織成頁;

          頁可以部分為空(并不要求每個page必須裝滿);

          頁面可以被分割在某個存儲體的不同的物理區(qū)域,也可以分布在不同的存儲體上,甚至是不同的網(wǎng)絡(luò)節(jié)點中。我們可以簡單假設(shè)每一個page都有一個唯一的地址標(biāo)識符PageAddress,并且操作系統(tǒng)可以根據(jù)PageAddress為我們定位該Page。

          一般情況下,使用page在其所在文件中的偏移量就可以表示了。




          往期精彩推薦



          騰訊、阿里、滴滴后臺面試題匯總總結(jié) — (含答案)

          面試:史上最全多線程面試題 !

          最新阿里內(nèi)推Java后端面試題

          JVM難學(xué)?那是因為你沒認真看完這篇文章


          END


          關(guān)注作者微信公眾號 —《JAVA爛豬皮》


          了解更多java后端架構(gòu)知識以及最新面試寶典


          你點的每個好看,我都認真當(dāng)成了


          看完本文記得給作者點贊+在看哦~~~大家的支持,是作者源源不斷出文的動力


          作者:等你歸去來

          出處:https://www.cnblogs.com/yougewe/p/9901758.html

          瀏覽 65
          點贊
          評論
          收藏
          分享

          手機掃一掃分享

          分享
          舉報
          評論
          圖片
          表情
          推薦
          點贊
          評論
          收藏
          分享

          手機掃一掃分享

          分享
          舉報
          <kbd id="afajh"><form id="afajh"></form></kbd>
          <strong id="afajh"><dl id="afajh"></dl></strong>
            <del id="afajh"><form id="afajh"></form></del>
                1. <th id="afajh"><progress id="afajh"></progress></th>
                  <b id="afajh"><abbr id="afajh"></abbr></b>
                  <th id="afajh"><progress id="afajh"></progress></th>
                  青青操久操视频 | 成人黄视频在线 | 五月婷色 | 日本激情视频一区二区三区 | 青青草免费在线公开视频 |