MySQL性能優(yōu)化

• 1、數(shù)據(jù)結(jié)構(gòu)前言
• 2、常見的數(shù)據(jù)結(jié)構(gòu)
• • 2.1 線性表
  • • 2.1.1 數(shù)組
    • 2.1.2 鏈表
    • 2.1.3 棧
    • 2.1.4 隊列
  • 2.2 散列表
  • 2.3 樹
  • • 2.3.1 二叉樹
  • 2.4 圖

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、成都微信小程序、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了鄆城免費(fèi)建站歡迎大家使用！1、數(shù)據(jù)結(jié)構(gòu)前言

數(shù)據(jù)結(jié)構(gòu)(data structure)是計算機(jī)存儲、組織數(shù)據(jù)的方式。是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合。“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系，分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。 我們討論的大多是邏輯結(jié)構(gòu)
數(shù)據(jù)邏輯結(jié)構(gòu)
指反映數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)，其中的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系，而與他們在計算機(jī)中的存儲位置無關(guān)。邏輯結(jié)構(gòu)包括：
1.集合：數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個集合” 的相互關(guān)系外，別無其他關(guān)系；
2.線性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對一的相互關(guān)系；
3.樹形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在一對多的相互關(guān)系；
4.圖形結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)中的元素存在多對多的相互關(guān)系。
數(shù)據(jù)物理結(jié)構(gòu)
數(shù)據(jù)的物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示（又稱映像），它包括數(shù)據(jù)元素的機(jī)內(nèi)表示和關(guān)系的機(jī)內(nèi)表示。由于具體實(shí)現(xiàn)的方法有順序、鏈接、索引、散列等多種，所以，一種數(shù)據(jù)結(jié)構(gòu)可表示成一種或多種存儲結(jié)構(gòu)。
數(shù)據(jù)元素的機(jī)內(nèi)表示（映像方法）： 用二進(jìn)制位（bit）的位串表示數(shù)據(jù)元素。通常稱這種位串為節(jié)點(diǎn)（node）。當(dāng)數(shù)據(jù)元素有若干個數(shù)據(jù)項(xiàng)組成時，位串中與各個數(shù)據(jù)項(xiàng)對應(yīng)的子位串稱為數(shù)據(jù)域（data field）。因此，節(jié)點(diǎn)是數(shù)據(jù)元素的機(jī)內(nèi)表示（或機(jī)內(nèi)映像）。
關(guān)系的機(jī)內(nèi)表示（映像方法）：數(shù)據(jù)元素之間的關(guān)系的機(jī)內(nèi)表示可以分為順序映像和非順序映像，常用兩種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)。順序映像借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。非順序映像借助指示元素存儲位置的指針（pointer）來表示數(shù)據(jù)元素之間的邏輯關(guān)系。
數(shù)據(jù)存儲結(jié)構(gòu)
數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)存儲空間中的存放形式稱為數(shù)據(jù)的物理結(jié)構(gòu)(也稱為存儲結(jié)構(gòu))。一般來說，一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲結(jié)構(gòu)，常用的存儲結(jié)構(gòu)有順序存儲、鏈?zhǔn)酱鎯?、索引存儲和哈希存儲等?br />數(shù)據(jù)的順序存儲結(jié)構(gòu)的特點(diǎn)是：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系；非順序存儲的特點(diǎn)是：借助指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。

2、常見的數(shù)據(jù)結(jié)構(gòu)

2.1 線性表

線性表（Linear List）就是數(shù)據(jù)排成像一條線一樣的結(jié)構(gòu)，數(shù)據(jù)只有前后兩個方向

2.1.1 數(shù)組

概念
數(shù)組（Array）是有限個相同類型的變量所組成的有序集合，數(shù)組中的每一個變量被稱為元素。數(shù)組是
最為簡單、最為常用的數(shù)據(jù)結(jié)構(gòu)。
數(shù)組下標(biāo)從零開始(Why)
存儲原理
數(shù)組用一組連續(xù)的內(nèi)存空間來存儲一組具有相同類型的數(shù)據(jù)
時間復(fù)雜度
讀取和更新都是隨機(jī)訪問，所以是O(1)
插入數(shù)組擴(kuò)容的時間復(fù)雜度是O(n)，插入并移動元素的時間復(fù)雜度也是O(n)，綜合起來插入操作的時間
復(fù)雜度是O(n)。
刪除操作，只涉及元素的移動，時間復(fù)雜度也是O(n)
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：
數(shù)組擁有非常高效的隨機(jī)訪問能力，只要給出下標(biāo)，就可以用常量時間找到對應(yīng)元素
缺點(diǎn)：
插入和刪除元素方面。由于數(shù)組元素連續(xù)緊密地存儲在內(nèi)存中，插入、刪除元素都會導(dǎo)致大量元素被迫
移動，影響效率。 (ArrayList LinkedList )
申請的空間必須是連續(xù)的，也就是說即使有空間也可能因?yàn)闆]有足夠的連續(xù)空間而創(chuàng)建失敗
如果超出范圍，需要重新申請內(nèi)存進(jìn)行存儲，原空間就浪費(fèi)了
應(yīng)用
數(shù)組是基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用太廣泛了，ArrayList、Redis、消息隊列等等。

2.1.2 鏈表

概念
鏈表（linked list）是一種在物理上非連續(xù)、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點(diǎn)（node）所組成。
鏈表中數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)（鏈表中每一個元
素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時動態(tài)生成。每個結(jié)點(diǎn)包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)
域，另一個是存儲下一個結(jié)點(diǎn)地址的指針域。（百度百科）
常見的鏈表包括：單鏈表、雙向鏈表、循環(huán)鏈表

• 單鏈表
  單向鏈表的每一個節(jié)點(diǎn)又包含兩部分，一部分是存放數(shù)據(jù)的變量data，另一部分是指向下一個節(jié)
  點(diǎn)的指針next
• 雙向鏈表
  雙向鏈表的每一個節(jié)點(diǎn)除了擁有data和next指針，還擁有指向前置節(jié)點(diǎn)的prev指針。
• 循環(huán)鏈表
  鏈表的尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)形成一個環(huán)，稱為循環(huán)鏈表

存儲原理
數(shù)組在內(nèi)存中的存儲方式是順序存儲（連續(xù)存儲），鏈表在內(nèi)存中的存儲方式則是隨機(jī)存儲（鏈?zhǔn)酱?br />儲）。
鏈表的每一個節(jié)點(diǎn)分布在內(nèi)存的不同位置，依靠next指針關(guān)聯(lián)起來。這樣可以靈活有效地利用零散的碎
片空間。
時間復(fù)雜度
查找節(jié)點(diǎn) ： O(n)
插入節(jié)點(diǎn)：O(1)
更新節(jié)點(diǎn)：O(1)
刪除節(jié)點(diǎn)：O(1)
優(yōu)缺點(diǎn)
優(yōu)勢
插入、刪除、更新效率高
省空間
劣勢
查詢效率較低，不能隨機(jī)訪問
應(yīng)用
鏈表的應(yīng)用也非常廣泛，比如樹、圖、Redis的列表、LRU算法實(shí)現(xiàn)、消息隊列等

2.1.3 棧

概念
棧（stack）是一種線性數(shù)據(jù)結(jié)構(gòu)，棧中的元素只能先入后出（First In Last Out，簡稱FILO）。
最早進(jìn)入的元素存放的位置叫作棧底（bottom），最后進(jìn)入的元素存放的位置叫作棧頂 （top）。
存儲原理
棧既可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)

• 數(shù)組實(shí)現(xiàn)的棧也叫順序?；蜢o態(tài)棧
• 鏈表實(shí)現(xiàn)的棧也叫做鏈?zhǔn)綏；騽討B(tài)棧

時間復(fù)雜度
入棧和出棧的時間復(fù)雜度都是O(1)
支持動態(tài)擴(kuò)容的順序棧
當(dāng)數(shù)組空間不夠時，我們就重新申請一塊更大的內(nèi)存，將原來數(shù)組中數(shù)據(jù)統(tǒng)統(tǒng)拷貝過去。這樣就實(shí)現(xiàn)了
一個支持動態(tài)擴(kuò)容的數(shù)組，通過前面學(xué)過的知識，可以得知入棧的時間復(fù)雜度是O(n)
應(yīng)用
函數(shù)調(diào)用
每進(jìn)入一個函數(shù)，就會將臨時變量作為一個棧入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個函
數(shù)對應(yīng)的棧幀出棧
瀏覽器的后退功能
我們使用兩個棧，X 和 Y，我們把首次瀏覽的頁面依次壓入棧 X，當(dāng)點(diǎn)擊后退按鈕時，再依次從棧
X 中出棧，并將出棧的數(shù)據(jù)依次放入棧 Y。當(dāng)我們點(diǎn)擊前進(jìn)按鈕時，我們依次從棧 Y 中取出數(shù)據(jù)，
放入棧 X 中。當(dāng)棧 X 中沒有數(shù)據(jù)時，那就說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)棧 Y 中沒有數(shù)
據(jù)，那就說明沒有頁面可以點(diǎn)擊前進(jìn)按鈕瀏覽了

2.1.4 隊列

概念
隊列（queue）是一種線性數(shù)據(jù)結(jié)構(gòu)，隊列中的元素只能先入先出（First In First Out，簡稱 FIFO）。
隊列的出口端叫作隊頭（front），隊列的入口端叫作隊尾（rear）。
存儲原理
隊列這種數(shù)據(jù)結(jié)構(gòu)既可以用數(shù)組來實(shí)現(xiàn)，也可以用鏈表來實(shí)現(xiàn)
用數(shù)組實(shí)現(xiàn)時，為了入隊操作的方便，把隊尾位置規(guī)定為最后入隊元素的下一個位置
用數(shù)組實(shí)現(xiàn)的隊列叫作順序隊列
用鏈表實(shí)現(xiàn)的隊列叫作鏈?zhǔn)疥犃?br />時間復(fù)雜度
入隊和出隊都是O(1)
應(yīng)用
資源池、消息隊列、命令隊列等等

2.2 散列表

概念
散列表也叫作哈希表（hash table），這種數(shù)據(jù)結(jié)構(gòu)提供了鍵（Key）和值（Value）的映射關(guān)系。只要
給出一個Key，就可以高效查找到它所匹配的Value，時間復(fù)雜度接近于O(1)。
存儲原理
哈希函數(shù)
散列表在本質(zhì)上也是一個數(shù)組
散列表的Key則是以字符串類型為主的
通過hash函數(shù)把Key和數(shù)組下標(biāo)進(jìn)行轉(zhuǎn)換
作用是把任意長度的輸入通過散列算法轉(zhuǎn)換成固定類型、固定長度的散列值
以Java為例：

//數(shù)組下標(biāo)=取key的hashcode模數(shù)組的長度后的余數(shù)
index = HashCode (Key) % Array.length

int index=Math.abs("Hello".hashCode())%10; （0-9）

這是最簡單的計算方式
還有很多hash函數(shù)：CRC16、CRC32、siphash 、murmurHash、times 33等
此種Hash計算方式為固定Hash方式，也稱為傳統(tǒng)Hash
該方式在數(shù)組固定時，可以快速檢索
但當(dāng)數(shù)組長度變化時，需要重新計算數(shù)組下標(biāo)，此時根據(jù)key檢索將出現(xiàn)問題
所以說傳統(tǒng)Hash法雖然比較簡單，但不利于擴(kuò)展，如果要擴(kuò)展可以采用一致性Hash法
時間復(fù)雜度
寫操作： O(1) + O(m) = O(m) m為單鏈元素個數(shù)
讀操作：O(1) + O(m) m為單鏈元素個數(shù)
Hash沖突寫單鏈表：O(m)
Hash擴(kuò)容：O(n) n是數(shù)組元素個數(shù) rehash
Hash沖突讀單鏈表：O(m) m為單鏈元素個數(shù)
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：讀寫快
缺點(diǎn)：哈希表中的元素是沒有被排序的、Hash沖突、擴(kuò)容 重新計算
應(yīng)用
HashMap
位圖：位圖就是bitmap的縮寫。所謂bitmap，就是用每一位來存放某種狀態(tài)，適用于大規(guī)模數(shù)據(jù)，但數(shù)據(jù)狀態(tài)又不是很多的情況。通常是用來判斷某個數(shù)據(jù)存不存在的。在STL中有一個bitset容器，其實(shí)就是位圖。

2.3 樹

概念
樹（tree）是n（n≥0）個節(jié)點(diǎn)的有限集。
當(dāng)n=0時，稱為空樹。在任意一個非空樹中，有如下特點(diǎn)。
有且僅有一個特定的稱為根的節(jié)點(diǎn)。
當(dāng)n>1時，其余節(jié)點(diǎn)可分為m（m>0）個互不相交的有限集
每一個集合本身又是一個樹，并稱為根的子樹。

2.3.1 二叉樹

概念
二叉樹（binary tree）是樹的一種特殊形式。二叉，顧名思義，這種樹的每個節(jié)點(diǎn)最多有2個孩子節(jié)
點(diǎn)。注意，這里是最多有2個，也可能只有1個，或者沒有孩子節(jié)點(diǎn)。

• 滿二叉樹
  一個二叉樹的所有非葉子節(jié)點(diǎn)都存在左右孩子，并且所有葉子節(jié)點(diǎn)都在同一層級上，那么這個樹就
  是滿二叉樹
• 完全二叉樹
  對一個有n個節(jié)點(diǎn)的二叉樹，按層級順序編號，則所有節(jié)點(diǎn)的編號為從1到n。如果這個樹所有節(jié)點(diǎn)和同
  樣深度的滿二叉樹的編號為從1到n的節(jié)點(diǎn)位置相同，則這個二叉樹為完全二叉樹

滿二叉樹要求所有分支都是滿的；而完全二叉樹只需保證最后一個節(jié)點(diǎn)之前的節(jié)點(diǎn)都齊全即可
存儲
二叉樹屬于邏輯結(jié)構(gòu)，可以使用鏈表和數(shù)組進(jìn)行存儲。

• 鏈?zhǔn)酱鎯?br />二叉樹的每一個節(jié)點(diǎn)包含3部分
  存儲數(shù)據(jù)的data變量
  指向左孩子的left指針
  指向右孩子的right指針
• 數(shù)組存儲
  使用數(shù)組存儲時，會按照層級順序把二叉樹的節(jié)點(diǎn)放到數(shù)組中對應(yīng)的位置上。
  如果某一個節(jié)點(diǎn)的左孩子或右孩子空缺，則數(shù)組的相應(yīng)位置也空出來
  尋址方式：
  一個父節(jié)點(diǎn)的下標(biāo)是n，那么它的左孩子節(jié)點(diǎn)下標(biāo)就是2×n+1、右孩子節(jié)點(diǎn)下標(biāo)就是2*(n+1)
  對于一個稀疏的二叉樹（孩子不滿）來說，用數(shù)組表示法是非常浪費(fèi)空間的

所以二叉樹一般用鏈表存儲實(shí)現(xiàn)。（二叉堆除外）
時間復(fù)雜度
二叉查找樹的插入和查找時間復(fù)雜度為:O(logn)
極端情況下二叉查找樹退化成鏈表，時間復(fù)雜度為O(n)，所以需要平衡二叉查找樹。
應(yīng)用
非線性數(shù)據(jù)：菜單，組織結(jié)構(gòu)、家譜等等
線性數(shù)據(jù)：二叉查找樹
二叉查找樹是有序的，我們只需要中序遍歷，就可以在 O(n) 的時間復(fù)雜度內(nèi)，輸出有序的數(shù)據(jù)序列。
二叉查找樹的性能非常穩(wěn)定，擴(kuò)容很方便(鏈表實(shí)現(xiàn))

2.4 圖

概念
圖（Graph），是一種復(fù)雜的非線性表結(jié)構(gòu)。
圖中的元素我們就叫做頂點(diǎn)（vertex）
圖中的一個頂點(diǎn)可以與任意其他頂點(diǎn)建立連接關(guān)系。我們把這種建立的關(guān)系叫做邊（edge）
跟頂點(diǎn)相連接的邊的條數(shù)叫做度（degree）

圖這種結(jié)構(gòu)有很廣泛的應(yīng)用，比如社交網(wǎng)絡(luò)，電子地圖，多對多的關(guān)系就可以用圖來表示。
邊有方向的圖叫做有向圖，比如A點(diǎn)到B點(diǎn)的直線距離，微信的添加好友是雙向的
邊無方向的圖叫無向圖，比如網(wǎng)絡(luò)拓?fù)鋱D
帶權(quán)圖（weighted graph）。在帶權(quán)圖中，每條邊都有一個權(quán)重（weight），我們可以通過這個權(quán)重
來表示 一些可度量的值

存儲原理
圖最直觀的一種存儲方法就是，鄰接矩陣（Adjacency Matrix）。
鄰接矩陣的底層是一個二維數(shù)組

• 無向圖：如果頂點(diǎn) i 與頂點(diǎn) j 之間有邊，我們就將 A[i][j]和 A[j][i]標(biāo)記為 1
  

• 有向圖
  如果頂點(diǎn) i 到頂點(diǎn) j 之間，有一條箭頭從頂點(diǎn) i 指向頂點(diǎn) j 的邊，那我們就將 A[i][j]標(biāo)記為 1。同理，如
  果有一條箭頭從頂點(diǎn) j 指向頂點(diǎn) i 的邊，我們就將 A[j][i]標(biāo)記為 1
  

• 帶權(quán)圖
  數(shù)組中就存儲相應(yīng)的權(quán)重
  

時間復(fù)雜度
鄰接表
每個頂點(diǎn)都需要被訪問一次，時間復(fù)雜度是 O(V)；相連的頂點(diǎn)（也就是每條邊）也都要被訪問一次，加
起來就是 O(E)。因此整體時間復(fù)雜度就是 O(V+E)。
鄰接矩陣
V 個頂點(diǎn)，每次都要檢查每個頂點(diǎn)與其他頂點(diǎn)是否有聯(lián)系，因此時間復(fù)雜度是 O( V2)。
應(yīng)用
廣度優(yōu)先的搜索可以同時從起始點(diǎn)和終點(diǎn)開始進(jìn)行，稱之為雙端 BFS。這種算法往往可以大大地提高搜
索的效率。
社交網(wǎng)絡(luò)可以用圖來表示。這個問題就非常適合用圖的廣度優(yōu)先搜索算法來解決，因?yàn)閺V度優(yōu)先搜索是
層層往外推進(jìn)的。首先，遍歷與起始頂點(diǎn)最近的一層頂點(diǎn)，也就是用戶的一度好友，然后再遍歷與用戶
距離的邊數(shù)為 2 的頂點(diǎn)，也就是二度好友關(guān)系，以及與用戶距離的邊數(shù)為 3 的頂點(diǎn)，也就是三度好友關(guān)
系。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

名稱欄目：【算術(shù)】數(shù)據(jù)結(jié)構(gòu)-創(chuàng)新互聯(lián)
當(dāng)前地址：http://jinyejixie.com/article24/dehhje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供靜態(tài)網(wǎng)站、微信公眾號、建站公司、外貿(mào)建站、網(wǎng)站內(nèi)鏈、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)