原文連結
還記得剛上研究所學生的時候，導師常挂在嘴邊的一句話，“科研的基礎不過就是資料而已。”如今看來，無論是人文社科，還是自然科學，或許都可在一定程度上看作是資料的科學。
倘若剝開研究領域的外衣，将人的操作抽象出來，那麼科研的過程大概就是根據資料流動探索其中的未知資訊吧。當然科學研究的範疇涵蓋甚廣，也不是一兩句話能夠拎得清的。不過從這個角度上的闡述，也隻是為了引出資料的重要性。
在當今社會，充斥着大量的資料。從衆多APP上的賬戶資料到銀行信用體系等個人檔案，都離不開對大量資料的組織、存儲和管理。而這，便是資料庫存在的目的和價值。
目前資料庫的類型主要分為兩種，一種是關系型資料庫，另一種是非關系型資料庫（NoSQL）。而我們今天的主角MySQL就是關系型資料庫中的一種。
本文結構
一、關系型資料庫與NoSQL
關系型資料庫，顧名思義，是指存儲的資料之間具有關系。這種所謂的關系通常用二維表格中的行列來表示，即一個二維表的邏輯結構能夠反映表中資料的存儲關系。
概念總是拗口難懂的。那麼簡單來說，關系型資料庫的存儲就是按照表格進行的。資料的存儲實際上就是對一個或者多個表格的存儲。通過對這些表格進行分類、合并、連接配接或者選取等運算來實作對資料庫的管理。常見的關系型資料庫有MySQL、Oracle、DB2和SqlServer等。
非關系型資料庫（NoSQL）是相對于關系型資料庫的一種泛指，它的特點是去掉了關系型資料庫中的關系特性，進而可獲得更好的擴充性。NoSQL并沒有嚴格的存儲方式，但采用不同的存儲結構都是為了獲得更高的性能和更高的并發。
NoSQL根據存儲方式可分為四大類，鍵值存儲資料庫、列存儲資料庫、文檔型資料庫和圖形資料庫。這四種資料的存儲原理不盡相同，因而在應用場景上也有些許的差異。一般常用的有作為資料緩存的redis和分布式系統的HBase。目前常見的資料庫排名可見網站：
https://db-engines.com/en/ranking四種NoSQL的特點比較
關系型資料庫與非關系型資料庫本質上的差別就在于存儲的資料是否具有一定的邏輯關系，由此産生的兩類資料庫看的性能和優劣勢上也有一定的差別。二者對比可見下圖。
關系型資料庫與NoSQL的優缺點對比
二、MySQL簡介
1. 介紹
在關系型資料庫中，MySQL可以說是其中的王者。它是目前最流行的資料庫之一，由瑞典 MySQL AB 公司開發，目前屬于 Oracle 公司。MySQL資料庫具有以下幾個方面的優勢：
- 體積小、速度快；
- 代碼開源，采用了 GPL 協定，可以修改源碼來開發自己的 MySQL 系統；
- 支援大型的資料庫，可以處理擁有上千萬條記錄的大型資料庫；
- 使用标準的 SQL 資料語言形式，并采用優化的 SQL 查詢算法，有效地提高查詢速度；
- 使用 C 和 C++ 編寫，并使用多種編譯器進行測試，保證源代碼的可移植性；
- 可運作在多個系統上，并且支援多種語言；
- 核心程式采用完全的多線程程式設計，可以靈活地為使用者提供服務，充分利用CPU資源。
2. 邏輯架構
MySQL的邏輯架構可分為四層，包括連接配接層、服務層、引擎層和存儲層，各層的接口互動及作用如下圖所示。需要注意的是，由于本文将主要講解事務的實作原理，是以下文針對的都是InnoDB引擎下的情況。
連接配接層： 負責處理用戶端的連接配接以及權限的認證。
服務層： 定義有許多不同的子產品，包括權限判斷，SQL接口，SQL解析，SQL分析優化， 緩存查詢的處理以及部分内置函數執行等。MySQL的查詢語句在服務層内進行解析、優化、緩存以及内置函數的實作和存儲。
引擎層： 負責MySQL中資料的存儲和提取。MySQL中的伺服器層不管理事務，事務是由存儲引擎實作的。其中使用最為廣泛的存儲引擎為InnoDB，其它的引擎都不支援事務。
存儲層： 負責将資料存儲與裝置的檔案系統中。
MySQL的邏輯架構
3. MySQL事務
事務是MySQL差別于NoSQL的重要特征，是保證關系型資料庫資料一緻性的關鍵技術。事務可看作是對資料庫操作的基本執行單元，可能包含一個或者多個SQL語句。這些語句在執行時，要麼都執行，要麼都不執行。
事務的執行主要包括兩個操作，送出和復原。
送出：commit，将事務執行結果寫入資料庫。
復原：rollback，復原所有已經執行的語句，傳回修改之前的資料。
MySQL事務包含四個特性，号稱ACID四大天王。
原子性（Atomicity） ：語句要麼全執行，要麼全不執行，是事務最核心的特性，事務本身就是以原子性來定義的；實作主要基于undo log日志實作的。
持久性（Durability) ：保證事務送出後不會因為當機等原因導緻資料丢失；實作主要基于redo log日志。
隔離性（Isolation） ：保證事務執行盡可能不受其他事務影響；InnoDB預設的隔離級别是RR，RR的實作主要基于鎖機制、資料的隐藏列、undo log和類next-key lock機制。
一緻性（Consistency） ：事務追求的最終目标，一緻性的實作既需要資料庫層面的保障，也需要應用層面的保障。
原子性
事務的原子性就如原子操作一般，表示事務不可再分，其中的操作要麼都做，要麼都不做；如果事務中一個SQL語句執行失敗，則已執行的語句也必須復原，資料庫退回到事務前的狀态。隻有0和1，沒有其它值。
事務的原子性表明事務就是一個整體，當事務無法成功執行的時候，需要将事務中已經執行過的語句全部復原，使得資料庫回歸到最初未開始事務的狀态。
事務的原子性就是通過undo log日志進行實作的。當事務需要進行復原時，InnoDB引擎就會調用undo log日志進行SQL語句的撤銷，實作資料的復原。
持久性
事務的持久性是指當事務送出之後，資料庫的改變就應該是永久性的，而不是暫時的。這也就是說，當事務送出之後，任何其它操作甚至是系統的當機故障都不會對原來事務的執行結果産生影響。
事務的持久性是通過InnoDB存儲引擎中的redo log日志來實作的，具體實作思路見下文。
隔離性
原子性和持久性是單個事務本身層面的性質，而隔離性是指事務之間應該保持的關系。隔離性要求不同僚務之間的影響是互不幹擾的，一個事務的操作與其它事務是互相隔離的。
由于事務可能并不隻包含一條SQL語句，是以在事務的執行期間很有可能會有其它事務開始執行。是以多事務的并發性就要求事務之間的操作是互相隔離的。這一點跟多線程之間資料同步的概念有些類似。
鎖機制
事務之間的隔離，是通過鎖機制實作的。當一個事務需要對資料庫中的某行資料進行修改時，需要先給資料加鎖；加了鎖的資料，其它事務是不運作操作的，隻能等待目前事務送出或復原将鎖釋放。
鎖機制并不是一個陌生的概念，在許多場景中都會利用到不同實作的鎖對資料進行保護和同步。而在MySQL中，根據不同的劃分标準，還可将鎖分為不同的種類。
按照粒度劃分：行鎖、表鎖、頁鎖
按照使用方式劃分：共享鎖、排它鎖
按照思想劃分：悲觀鎖、樂觀鎖
鎖機制的知識點很多，由于篇幅不好全部展開講。這裡對按照粒度劃分的鎖進行簡單介紹。
粒度：指資料倉庫的資料機關中儲存資料的細化或綜合程度的級别。細化程度越高，粒度級就越小；相反，細化程度越低，粒度級就越大。
MySQL按照鎖的粒度劃分可以分為行鎖、表鎖和頁鎖。
行鎖：粒度最小的鎖，表示隻針對目前操作的行進行加鎖；
表鎖：粒度最大的鎖，表示目前的操作對整張表加鎖；
頁鎖：粒度介于行級鎖和表級鎖中間的一種鎖，表示對頁進行加鎖。
資料庫的粒度劃分
這三種鎖是在不同層次上對資料進行鎖定，由于粒度的不同，其帶來的好處和劣勢也不一而同。
表鎖在操作資料時會鎖定整張表，因而并發性能較差；
行鎖則隻鎖定需要操作的資料，并發性能好。但是由于加鎖本身需要消耗資源(獲得鎖、檢查鎖、釋放鎖等都需要消耗資源)，是以在鎖定資料較多情況下使用表鎖可以節省大量資源。
MySQL中不同的存儲引擎能夠支援的鎖也是不一樣的。MyIsam隻支援表鎖，而InnoDB同時支援表鎖和行鎖，且出于性能考慮，絕大多數情況下使用的都是行鎖。
并發讀寫問題
在并發情況下，MySQL的同時讀寫可能會導緻三類問題，髒讀、不可重複度和幻讀。
（1）髒讀：目前事務中讀到其他事務未送出的資料，也就是髒資料。
以上圖為例，事務A在讀取文章的閱讀量時，讀取到了事務B為送出的資料。如果事務B最後沒有順利送出，導緻事務復原，那麼實際上閱讀量并沒有修改成功，而事務A卻是讀到的修改後的值，顯然不合情理。
（2）不可重複讀：在事務A中先後兩次讀取同一個資料，但是兩次讀取的結果不一樣。髒讀與不可重複讀的差別在于：前者讀到的是其他事務未送出的資料，後者讀到的是其他事務已送出的資料。
以上圖為例，事務A在先後讀取文章閱讀量的資料時，結果卻不一樣。說明事務A在執行的過程中，閱讀量的值被其它事務給修改了。這樣使得資料的查詢結果不再可靠，同樣也不合實際。
（3）幻讀：在事務A中按照某個條件先後兩次查詢資料庫，兩次查詢結果的行數不同，這種現象稱為幻讀。不可重複讀與幻讀的差別可以通俗的了解為：前者是資料變了，後者是資料的行數變了。
以上圖為例，當對0<閱讀量<100的文章進行查詢時，先查到了一個結果，後來查詢到了兩個結果。這表明同一個事務的查詢結果數不一，行數不一緻。這樣的問題使得在根據某些條件對資料篩選的時候，前後篩選結果不具有可靠性。
隔離級别
根據上面這三種問題，産生了四種隔離級别，表明資料庫不同程度的隔離性質。
在實際的資料庫設計中，隔離級别越高，導緻資料庫的并發效率會越低；而隔離級别太低，又會導緻資料庫在讀寫過程中會遇到各種亂七八糟的問題。
是以在大多數資料庫系統中，預設的隔離級别時讀已送出（如Oracle）或者可重複讀RR（MySQL的InnoDB引擎）。
MVCC
又是一個難嚼的大塊頭。MVCC就是用來實作上面的第三個隔離級别，可重複讀RR。
MVCC：Multi-Version Concurrency Control，即多版本的并發控制協定。
MVCC的特點就是在同一時刻，不同僚務可以讀取到不同版本的資料，進而可以解決髒讀和不可重複讀的問題。
MVCC實際上就是通過資料的隐藏列和復原日志（undo log），實作多個版本資料的共存。這樣的好處是，使用MVCC進行讀資料的時候，不用加鎖，進而避免了同時讀寫的沖突。
在實作MVCC時，每一行的資料中會額外儲存幾個隐藏的列，比如目前行建立時的版本号和删除時間和指向undo log的復原指針。這裡的版本号并不是實際的時間值，而是系統版本号。每開始新的事務，系統版本号都會自動遞增。事務開始時的系統版本号會作為事務的版本号，用來和查詢每行記錄的版本号進行比較。
每個事務又有自己的版本号，這樣事務内執行資料操作時，就通過版本号的比較來達到資料版本控制的目的。
另外，InnoDB實作的隔離級别RR時可以避免幻讀現象的，這是通過
next-key lock
機制實作的。
next-key lock
實際上就是行鎖的一種，隻不過它不隻是會鎖住目前行記錄的本身，還會鎖定一個範圍。比如上面幻讀的例子，開始查詢0<閱讀量<100的文章時，隻查到了一個結果。
next-key lock
會将查詢出的這一行進行鎖定，同時還會對0<閱讀量<100這個範圍進行加鎖，這實際上是一種間隙鎖。間隙鎖能夠防止其他事務在這個間隙修改或者插入記錄。這樣一來，就保證了在0<閱讀量<100這個間隙中，隻存在原來的一行資料，進而避免了幻讀。
間隙鎖：封鎖索引記錄中的間隔
雖然InnoDB使用
next-key lock
能夠避免幻讀問題，但卻并不是真正的可串行化隔離。再來看一個例子吧。
首先提一個問題：
在T6時間，事務A送出事務之後，猜一猜文章A和文章B的閱讀量為多少？
答案是，文章AB的閱讀量都被修改成了10000。這代表着事務B的送出實際上對事務A的執行産生了影響，表明兩個事務之間并不是完全隔離的。雖然能夠避免幻讀現象，但是卻沒有達到可串行化的級别。
這還說明，避免髒讀、不可重複讀和幻讀，是達到可串行化的隔離級别的必要不充分條件。可串行化是都能夠避免髒讀、不可重複讀和幻讀，但是避免髒讀、不可重複讀和幻讀卻不一定達到了可串行化。
一緻性
一緻性是指事務執行結束後，資料庫的完整性限制沒有被破壞，事務執行的前後都是合法的資料狀态。
一緻性是事務追求的最終目标，原子性、持久性和隔離性，實際上都是為了保證資料庫狀态的一緻性而存在的。
這就不多說了吧。你細品。
四、 MySQL日志系統
了解完MySQL的基本架構，大體上能夠對MySQL的執行流程有了比較清晰的認知。接下來我将為大家介紹一下日志系統。
MySQL日志系統是資料庫的重要元件，用于記錄資料庫的更新和修改。若資料庫發生故障，可通過不同日志記錄恢複資料庫的原來資料。是以實際上日志系統直接決定着MySQL運作的魯棒性和穩健性。
MySQL的日志有很多種，如二進制日志（binlog）、錯誤日志、查詢日志、慢查詢日志等，此外InnoDB存儲引擎還提供了兩種日志：redo log（重做日志）和undo log（復原日志）。這裡将重點針對InnoDB引擎，對重做日志、復原日志和二進制日志這三種進行分析。
1. 重做日志（redo log）
重做日志（redo log）是InnoDB引擎層的日志，用來記錄事務操作引起資料的變化，記錄的是資料頁的實體修改。
重做日記的作用其實很好了解，我打個比方。資料庫中資料的修改就好比你寫的論文，萬一哪天論文丢了怎麼呢？以防這種不幸的發生，我們可以在寫論文的時候，每一次修改都拿個小本本記錄一下，記錄什麼時間對某一頁進行了怎麼樣的修改。這就是重做日志。
InnoDB引擎對資料的更新，是先将更新記錄寫入redo log日志，然後會在系統空閑的時候或者是按照設定的更新政策再将日志中的内容更新到磁盤之中。這就是所謂的預寫式技術（Write Ahead logging）。這種技術可以大大減少IO操作的頻率，提升資料重新整理的效率。
髒資料刷盤
值得注意的是，redo log日志的大小是固定的，為了能夠持續不斷的對更新記錄進行寫入，在redo log日志中設定了兩個标志位置，checkpoint和write_pos，分别表示記錄擦除的位置和記錄寫入的位置。redo log日志的資料寫入示意圖可見下圖。
當
write_pos
标志到了日志結尾時，會從結尾跳至日志頭部進行重新循環寫入。是以redo log的邏輯結構并不是線性的，而是可看作一個圓周運動。
write_pos
與
heckpoint
中間的空間可用于寫入新資料，寫入和擦除都是往後推移，循環往複的。
write_pos
追上
checkpoint
時，表示redo log日志已經寫滿。這時不能繼續執行新的資料庫更新語句，需要停下來先删除一些記錄，執行
checkpoint
規則騰出可寫空間。
checkpoint規則：checkpoint觸發後，将buffer中髒資料頁和髒日志頁都刷到磁盤。
髒資料：指記憶體中未刷到磁盤的資料。
redo log中最重要的概念就是緩沖池
buffer pool
，這是在記憶體中配置設定的一個區域，包含了磁盤中部分資料頁的映射，作為通路資料庫的緩沖。
當請求讀取資料時，會先判斷是否在緩沖池命中，如果未命中才會在磁盤上進行檢索後放入緩沖池；
當請求寫入資料時，會先寫入緩沖池，緩沖池中修改的資料會定期重新整理到磁盤中。這一過程也被稱之為刷髒 。
是以，當資料修改時，除了修改
buffer pool
中的資料，還會在redo log中記錄這次操作；當事務送出時，會根據redo log的記錄對資料進行刷盤。如果MySQL當機，重新開機時可以讀取redo log中的資料，對資料庫進行恢複，進而保證了事務的持久性，使得資料庫獲得
crash-safe
能力。
髒日志刷盤
除了上面提到的對于髒資料的刷盤，實際上redo log日志在記錄時，為了保證日志檔案的持久化，也需要經曆将日志記錄從記憶體寫入到磁盤的過程。redo log日志可分為兩個部分，一是存在易失性記憶體中的緩存日志
redo log buff
，二是儲存在磁盤上的redo log日志檔案
redo log file
。
為了確定每次記錄都能夠寫入到磁盤中的日志中，每次将
redo log buffer
中的日志寫入
redo log file
的過程中都會調用一次作業系統的
fsync
操作。
fsync函數：包含在UNIX系統頭檔案#include 中，用于同步記憶體中所有已修改的檔案資料到儲存裝置。
在寫入的過程中，還需要經過作業系統核心空間的
os buffer
。redo log日志的寫入過程可見下圖。
redo log日志刷盤流程
2. 二進制日志（binlog）
二進制日志binlog是服務層的日志，還被稱為歸檔日志。binlog主要記錄資料庫的變化情況，内容包括資料庫所有的更新操作。所有涉及資料變動的操作，都要記錄進二進制日志中。是以有了binlog可以很友善的對資料進行複制和備份，因而也常用作主從庫的同步。
這裡binlog所存儲的内容看起來似乎與redo log很相似，但是其實不然。redo log是一種實體日志，記錄的是實際上對某個資料進行了怎麼樣的修改；而binlog是邏輯日志，記錄的是SQL語句的原始邏輯，比如”給ID=2這一行的a字段加1 “。binlog日志中的内容是二進制的，根據日記格式參數的不同，可能基于SQL語句、基于資料本身或者二者的混合。一般常用記錄的都是SQL語句。
這裡的實體和邏輯的概念，我的個人了解是：
實體的日志可看作是實際資料庫中資料頁上的變化資訊，隻看重結果，而不在乎是通過“何種途徑”導緻了這種結果；
邏輯的日志可看作是通過了某一種方法或者操作手段導緻資料發生了變化，存儲的是邏輯性的操作。
同時，redo log是基于
crash recovery
，保證MySQL當機後的資料恢複；而binlog是基于
point-in-time recovery
，保證伺服器可以基于時間點對資料進行恢複，或者對資料進行備份。
事實上最開始MySQL是沒有redo log日志的。因為起先MySQL是沒有InnoDB引擎的，自帶的引擎是MyISAM。binlog是服務層的日志，是以所有引擎都能夠使用。但是光靠binlog日志隻能提供歸檔的作用，無法提供
crash-safe
能力，是以InnoDB引擎就采用了學自于Oracle的技術，也就是redo log，這才擁有了
crash-safe
能力。這裡對redo log日志和binlog日志的特點分别進行了對比：
redo log與binlog的特點比較
在MySQL執行更新語句時，都會涉及到redo log日志和binlog日志的讀寫。一條更新語句的執行過程如下：
MySQL更新語句的執行過程
從上圖可以看出，MySQL在執行更新語句的時候，在服務層進行語句的解析和執行，在引擎層進行資料的提取和存儲；同時在服務層對binlog進行寫入，在InnoDB内進行redo log的寫入。
不僅如此，在對redo log寫入時有兩個階段的送出，一是binlog寫入之前prepare狀态的寫入，二是binlog寫入之後commit狀态的寫入。
之是以要安排這麼一個兩階段送出，自然是有它的道理的。現在我們可以假設不采用兩階段送出的方式，而是采用“單階段”進行送出，即要麼先寫入redo log，後寫入binlog；要麼先寫入binlog，後寫入redo log。這兩種方式的送出都會導緻原先資料庫的狀态和被恢複後的資料庫的狀态不一緻。
先寫入redo log，後寫入binlog：
在寫完redo log之後，資料此時具有crash-safe能力，是以系統崩潰，資料會恢複成事務開始之前的狀态。但是，若在redo log寫完時候，binlog寫入之前，系統發生了當機。此時binlog沒有對上面的更新語句進行儲存，導緻當使用binlog進行資料庫的備份或者恢複時，就少了上述的更新語句。進而使得
id=2
這一行的資料沒有被更新。
先寫binlog後寫redo log的問題
由此可見，兩階段的送出就是為了避免上述的問題，使得binlog和redo log中儲存的資訊是一緻的。
3. 復原日志（undo log）
復原日志同樣也是InnoDB引擎提供的日志，顧名思義，復原日志的作用就是對資料進行復原。當事務對資料庫進行修改，InnoDB引擎不僅會記錄redo log，還會生成對應的undo log日志；如果事務執行失敗或調用了rollback，導緻事務需要復原，就可以利用undo log中的資訊将資料復原到修改之前的樣子。
但是undo log不redo log不一樣，它屬于邏輯日志。它對SQL語句執行相關的資訊進行記錄。當發生復原時，InnoDB引擎會根據undo log日志中的記錄做與之前相反的工作。比如對于每個資料插入操作（insert），復原時會執行資料删除操作（delete）；對于每個資料删除操作（delete），復原時會執行資料插入操作（insert）；對于每個資料更新操作（update），復原時會執行一個相反的資料更新操作（update），把資料改回去。undo log由兩個作用，一是提供復原，二是實作MVCC。
五、主從複制
主從複制的概念很簡單，就是從原來的資料庫複制一個完全一樣的資料庫，原來的資料庫稱作主資料庫，複制的資料庫稱為從資料庫。從資料庫會與主資料庫進行資料同步，保持二者的資料一緻性。
主從複制的原理實際上就是通過bin log日志實作的。bin log日志中儲存了資料庫中所有SQL語句，通過對bin log日志中SQL的複制，然後再進行語句的執行即可實作從資料庫與主資料庫的同步。
主從複制的過程可見下圖。主從複制的過程主要是靠三個線程進行的，一個運作在主伺服器中的發送線程，用于發送binlog日志到從伺服器。兩外兩個運作在從伺服器上的I/O線程和SQL線程。I/O線程用于讀取主伺服器發送過來的binlog日志内容，并拷貝到本地的中繼日志中。SQL線程用于讀取中繼日志中關于資料更新的SQL語句并執行，進而實作主從庫的資料一緻。
主從複制原理
之是以需要實作主從複制，實際上是由實際應用場景所決定的。主從複制能夠帶來的好處有：
- 通過複制實作資料的異地備份，當主資料庫故障時，可切換從資料庫，避免資料丢失。
- 可實作架構的擴充，當業務量越來越大，I/O通路頻率過高時，采用多庫的存儲，可以降低磁盤I/O通路的頻率，提高單個機器的I/O性能。
- 可實作讀寫分離，使資料庫能支援更大的并發。
- 實作伺服器的負載均衡，通過在主伺服器和從伺服器之間切分處理客戶查詢的負荷。
六、總結
MySQL資料庫應該算是程式員必須掌握的技術之一了。無論是項目過程中還是面試中，MySQL都是非常重要的基礎知識。不過，對于MySQL來說，真的東西太多了。我在寫這篇文章的時候，查閱了大量的資料，發現越看不懂的越多。還真是應了那句話：
你知道的越多，不知道的也就越多。
這篇文章着重是從理論的角度去解析MySQL基本的事務和日志系統的基本原理，我在表述的時候盡可能的避免采用實際的代碼去描述。即便是這篇将近一萬字+近二十副純手工繪制的圖解，也難以将MySQL的博大精深分析透徹。
但是我相信，對于初學者而言，這些理論能夠讓你對MySQL有一個整體的感覺，讓你對“何謂關系型資料庫”這麼一個問題有了比較清晰的認知；而對于熟練掌握MySQL的大佬來說，或許本文也能夠喚醒你塵封已久的底層理論基礎，對你之後的面試也會有一定幫助。
技術這種東西沒有絕對的對錯，倘若文中有誤還請諒解，并歡迎與我讨論。自主思考永遠比被動接受更有效。
七、 Reference
- https://www.cnblogs.com/kismetv/p/10331633.html
- https://www.cnblogs.com/ivy-zheng/p/11094528.html
- https://blog.csdn.net/qq_39016934/article/details/90116706
- https://www.jianshu.com/p/5af73b203f2a
- https://www.cnblogs.com/f-ck-need-u/archive/2018/05/08/9010872.html#auto_id_2
來源 | 五分鐘學算法
作者 | 程式員小吳