學(xué)習(xí)地址：【數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)-java版】? ? ? ? ? ? ? ? ??🚀數(shù)據(jù)結(jié)構(gòu)--Java專欄🚀

• 筆記01【01-09】【概述、數(shù)組基本使用】【源碼、課件】
• 筆記02【10-18】【棧、隊列、單鏈表(增刪節(jié)點)、循環(huán)鏈表、雙向循環(huán)鏈表、遞歸(斐波那契、漢諾塔)】
• 筆記03【19-27】【（時間、空間復(fù)雜度）；八大排序（冒泡、快速、插入、希爾、選擇、歸并、基數(shù)、隊列基數(shù)）】
• 筆記04【28-33】【樹結(jié)構(gòu)(二叉樹)概述、創(chuàng)建、遍歷、查找節(jié)點、刪除節(jié)點】
• 筆記05【34-39】【順序存儲二叉樹概述、二叉樹遍歷、堆排序、線索二叉樹實現(xiàn)及遍歷】
• 筆記06【40-48】【赫夫曼樹、概述、原理分析、代碼實現(xiàn)(數(shù)據(jù)壓縮、創(chuàng)建編碼表、解碼、壓縮文件、解壓文件)】
• 筆記07【49-54】【二叉排序樹（添加、查找、刪除節(jié)點）】
• 筆記08【55-57】【二叉平衡樹(AVL)-概述、單旋轉(zhuǎn)、雙旋轉(zhuǎn)】
• 筆記09【58-60】【計算機(jī)中數(shù)據(jù)的存儲原理、2-3樹的插入原理、B樹和B+樹】
• 筆記10【61-63】【哈希表概述、散列函數(shù)的設(shè)計、散列沖突解決方案】
• 筆記11【64-67】【圖結(jié)構(gòu)概述、圖遍歷原理(BFS\DFS)、圖遍歷代碼實現(xiàn)】

目? ?錄

P58 4.31 計算機(jī)中數(shù)據(jù)的存儲原理

P59 4.32 2-3樹的插入原理

1、2-3樹

2、詳細(xì)案例求解過程

P60 4.33 B樹和B+樹原理

---

P58 4.31 計算機(jī)中數(shù)據(jù)的存儲原理

樹的數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用場景：內(nèi)存（數(shù)據(jù)量少！）。

數(shù)據(jù)量大，不能直接存在內(nèi)存中 --> 存儲到硬盤中。

硬盤：機(jī)械硬盤、固態(tài)硬盤。

機(jī)械硬盤的存儲介質(zhì)：磁盤。

讀取速度：內(nèi)存 > 固態(tài)硬盤 > 機(jī)械硬盤

磁盤固定于主軸之上；一個主軸上，可以固定幾個磁盤。磁盤上下分為兩面。

磁盤的盤面，分為一圈圈；每一圈 稱為 磁道。使用間隔（gap）可以將磁道分為若干個扇區(qū)（sector）。

數(shù)據(jù)存儲在扇區(qū)中。

硬盤讀取磁盤數(shù)據(jù)：傳動臂頂上的磁頭 在磁盤上 讀取數(shù)據(jù)。

傳動臂可以進(jìn)行一定的擺動，磁盤進(jìn)行轉(zhuǎn)動。磁盤轉(zhuǎn)動速度：7200轉(zhuǎn)/min、5400轉(zhuǎn)/min。

磁盤的轉(zhuǎn)動集合傳動臂的擺動，可以讀取磁盤盤面上的任何一個扇區(qū)的內(nèi)容。

二叉樹：每個節(jié)點存儲一個值。數(shù)據(jù)量大，樹的高度會非常高。

節(jié)點數(shù)多，導(dǎo)致I/O操作多，速度慢！

==>

將節(jié)點進(jìn)行拓展。（根節(jié)點：3個值；子節(jié)點：7個值。只有5個節(jié)點，最多2次I/O操作。）

P59 4.32 2-3樹的插入原理

1、2-3樹

2-3樹是最簡單的B-樹（或-樹）結(jié)構(gòu)，其每個非葉節(jié)點都有兩個或三個子女，而且所有葉都在統(tǒng)一層上。2-3樹不是二叉樹，其節(jié)點可擁有3個孩子。不過，2-3樹與滿二叉樹相似。高為h的2-3樹包含的節(jié)點數(shù)大于等于高度為h的滿二叉樹的節(jié)點數(shù)，即至少有2^h-1個節(jié)點。

2、詳細(xì)案例求解過程

2-3樹（B樹特例）：對節(jié)點進(jìn)行拓展。

2-3樹（3階B樹）：每放入一個數(shù)，都要保證是B樹！！！【把 三節(jié)點 拆分為 兩個 二節(jié)點。】【下面放不下的，往上放。】

中序遍歷---有序集合

P60 4.33 B樹和B+樹原理

2-3-4樹（4階B樹）

B+樹：B樹的變形，可以 通過 索引信息 快速地 找到 想要的數(shù)據(jù)。

MySQL數(shù)據(jù)庫（2種引擎：B樹、B+樹）

總結(jié)

以上是生活随笔為你收集整理的数据结构Java09【计算机中数据的存储原理、2-3树的插入原理、B树和B+树】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。