摘要：每個列表中的數據項稱為元素。棧被稱為一種后入先出，的數據結構。散列使用的數據結構叫做散列表。不包含任何成員的集合稱為空集，全集則是包含一切可能成員的集合。因此二叉搜索樹需要平衡，即左右子樹高度要相近。

樓樓非計算機專業，但是對計算機也還算喜歡。個人理解若有偏差，歡迎各位批評指正！

對于數據結構和算法一直是我的薄弱環節，相信大多數前端工程師可能多少會有些這方面的弱點，加上數據結構和算法本來就有些枯燥，立下個flag，三天過后拋之腦后的也時有發生，好了，收起老媽子的叨叨叨，畢竟樓樓還是個美少女，哈哈哈~

在JS中，我所知的稍微復雜點的數據結構有數組和對象。

但是統觀大多數語言，就會發現自己知道的太少了，當然以下涉及到的我們可能會用的很少。但是個人認為這些是思想上的沉淀，所發生的的變化帶給自己的影響也將會是潛移默化的，就當是潤物細無聲了，哈哈哈~

樓樓借鑒了數據結構與算法JavaScript描述一書，在寫這篇帖子時~

==開始----------------------------------------------------------------------------------------------==

數組：

一個存儲元素的線性集合（collection），元素可以通過索引來任意存取，索引通常是數字，用來計算元素之間存儲位置的偏移量。

數組的那些方法（js）

es6新增
Array.from()//偽數組轉數組  不支持的話我們還可以通過call和apply改變this指向，從而達到偽數組調用數組的方法
Array.of() //將一組值，轉換為數組
Array.prototype.copyWithin(target, start = 0, end = this.length) //指定位置的成員復制到其他位置（會覆蓋原有成員），然后返回當前數組。也就是說，使用這個方法，會修改當前數組。
    target（必需）：從該位置開始替換數據。如果為負值，表示倒數。
    start（可選）：從該位置開始讀取數據，默認為 0。如果為負值，表示倒數。
    end（可選）：到該位置前停止讀取數據，默認等于數組長度。如果為負值，表示倒數。
Array.find(item => item > 0) 找到數組中符合條件的元素返回，如果沒有符合條件的元素返回undefine
Array.findIndex(item => item > 0) 返回第一個符合條件的數組成員的位置，如果所有成員都不符合條件，則返回-1。
Array.fill() //使用一個值來填充數組
entries()【對鍵值】 keys()【對鍵】 values()【對值】 用于遍歷數組。他們都返回一個遍歷器對象。
Array.includes() 這個方法必須力推，返回布爾值，表示某個數組是否包含特定的值，與字符串includes方法類似
    
另外還有這些，就不一一贅述了
join()  push()和pop() shift() 和 unshift() sort()  reverse()  concat()  slice()
splice()  indexOf()和 lastIndexOf() （ES5新增） forEach() （ES5新增）  map() （ES5新增）
filter() （ES5新增）  every() （ES5新增）  some() （ES5新增） reduce()和 reduceRight() （ES5新增）

數組中較為復雜的應為二維和多維數組。

JavaScript 只支持一維數組，但是通過在數組里保存數組元素的方式，可以輕松創建多維數組。

列表

列表是一組有序的數據。每個列表中的數據項稱為元素。在 JavaScript 中，列表中的元素可以是任意數據類型。列表中可以保存多少元素并沒有事先限定，實際使用時元素的數量受到程序內存的限制。列表有前有后（分別對應 front 和 end）。

棧

棧是一種特殊的列表，棧內的元素只能通過列表的一端訪問，這一端稱為棧頂。棧被稱為一種后入先出（LIFO，last-in-first-out）的數據結構。入棧使用 push() 方法，出棧使用 pop() 方法。

隊列

隊列是一種先進先出（First-In-First-Out，FIFO）的數據結構。插入操作也叫做入隊，刪除操作也叫做出隊。入隊操作在隊尾插入新元素，出隊操作刪除隊頭的元素。

鏈表

==背景：在很多編程語言中，數組的長度是固定的，所以當數組已被數據填滿時，再要加入新的元素就會非常困難。在數組中，添加和刪除元素也很麻煩，因為需要將數組中的其他元素向前或向后平移，以反映數組剛剛進行了添加或刪除操作。然而JavaScript 的數組并不存在上述問題，因為使用 split() 方法不需要再訪問數組中的其他元素了。==
鏈表是由一組節點組成的集合。每個節點都使用一個對象的引用指向它的后繼。指向另一個節點的引用叫做鏈。

我們常說的鏈表是單向鏈表

雙向鏈表示意圖：

循環鏈表示意圖

通過這三個圖片希望你對鏈表有初步認知。

字典

字典是一種以鍵 - 值對形式存儲數據的數據結構，一般大家談到字典會說到電話簿，我覺得在JS里他更像是Object類，一個鍵對應一個值。但是很多教材中會說，Dictionay 類的基礎是 Array 類，而不是 Object 類。OK，That"s OK! 畢竟JavaScript中萬物皆對象。

散列

散列是一種常用的數據存儲技術，散列后的數據可以快速地插入或取用。散列使用的數據結構叫做散列表。在散列表上插入刪除和取用數據都非常快，但是對于查找操作來說卻效率低下，比如查找一組數據中的最大值和最小值。這些操作得求助于其他數據結構，二叉查找樹就是一個很好的選擇。

即使使用一個高效的散列函數，仍然存在將兩個鍵映射成同一個值的可能，這種現象稱為碰撞（collision）

==hashTable的實現就是典型的基于散列的一種數據結構，在這里有興趣的話還可以去看一下霍納算法==

當散列函數對于多個輸入產生同樣的輸出時，就產生了碰撞。

碰撞的解決方法：開鏈法和線性探測法

開鏈法是指實現散列表的底層數組中，每個數組元素又是一個新的數據結構，比如另一個數組，這樣就能存儲多個鍵了。使用這種技術，即使兩個鍵散列后的值相同，依然被保存在同樣的位置，只不過它們在第二個數組中的位置不一樣罷了。

線性探測法隸屬于一種更一般化的散列技術：開放尋址散列。當發生碰撞時，線性探測法檢查散列表中的下一個位置是否為空。如果為空，就將數據存入該位置；如果不為空，則繼續檢查下一個位置，直到找到一個空的位置為止。該技術是基于這樣一個事實：每個散列表都會有很多空的單元格，可以使用它們來存儲數據。

集合

集合是由一組無序但彼此之間又有一定相關性的成員構成的，每個成員在集合中只能出現一次。

? 不包含任何成員的集合稱為空集，全集則是包含一切可能成員的集合。
? 如果兩個集合的成員完全相同，則稱兩個集合相等。
? 如果一個集合中所有的成員都屬于另外一個集合，則前一集合稱為后一集合的子集。

對集合的基本操作有下面幾種。

? 并集
將兩個集合中的成員進行合并，得到一個新集合。
? 交集
兩個集合中共同存在的成員組成一個新的集合。
? 補集
屬于一個集合而不屬于另一個集合的成員組成的

樹：

樹是一種非線性的數據結構，以分層的方式來存儲數據。

樹：

樹是一種非線性的數據結構，以分層的方式來存儲數據。
其中樹里面常被提起的應當是二叉樹。提起二叉樹補充一些，這是我一個朋友寫的，感覺寫的比較好。拿出來分享一下~
表達順序集比較合適的數據結構樹。。。樹最合適。為什么？

    二叉搜索樹天然可用于排序的二分查找，左子樹小于根節點，右子樹大于根節點，樹的高度即為最大搜索次數，是很小的常數。
    二叉搜索樹 改進為 二叉平衡搜索樹
    二叉搜索樹有什么劣勢？樹的構建受數據集合的順序影響，極端情況下，蛻化為單項鏈表，失去二叉樹的意義，檢索復雜度退化到順序遍歷。
    因此二叉搜索樹需要平衡，即左右子樹高度要相近。
二叉平衡搜索樹 改進為 B樹
    搜索復雜度為 log2 (n)，要想進一步降低搜索次數即樹高度，怎么辦？增大對數的底，底越大，對數值越小。
    因此改進為 m 階樹，并對非根節點的key個數進行約定(m/2 ~ m)，成為B樹。
B樹 改進為 B+樹
    B樹的劣勢：B樹每個節點包含數據記錄本身或指針，內存空間占用大，反復換頁導致訪存低效；典型業務場景查詢的都是一段范圍的數據記錄，不僅僅是單條，B樹比較慢。
    改進措施：樹的非葉子節點不包含數據記錄，葉子節點包含數據記錄的指針（聚集索引的key），整體減小索引樹占用的內存，提高訪存效率；所有數據記錄被葉子節點覆蓋，葉子節點天然是有序的，以單項鏈表連接，很方便遍歷一段范圍的記錄。
改進后即為 B+ 樹。mariadb-10.3使用的即為B+樹。
B+樹 改進為 B*樹
    B+樹的劣勢：每個非葉子節點可能只包含 m/2 個key，有一半空閑，內存使用率低。
    改進措施：將非葉子節點的最小key數增加為 2m/3，提高內存使用率。付出的代價是需要對非葉子節點增加指向兄弟的指針，以便于節點拆分、合并。
    改進后即為 B* 樹。
基于B+樹的一些推論
select * from xxx offset N limit M，不用特別在意N對效率的影響。如果N可能很大，例如過萬，區分維護冷、熱數據，確保N不會太大。
select * from xxx order by a order by b，聯合索引受索引樹的影響，天然要求左匹配原則，能利用到聯合索引時查找效率很高。
主鍵用 uuid 還是 int 更好？innobase數據引擎下單調增長的 int 更好。uuid 32字節，用于索引必然比 int 4字節大，索引樹占用的內存越大訪存效率越低，所以 uuid 差；innobase的文件物理存儲結構內涵為主鍵索引（聚集索引），單調遞增的主鍵確保在連續的disk page 上不斷 append 數據，訪存效率高，而uuid導致新增數據隨機插入disk page，需要大量移動數據，訪存效率低?？傮w上看uuid較差。當然id本身也存在生成時的鎖競爭等問題。

對于樹結構有興趣的可以再深入探討，因為這塊確實水比較深

圖和圖算法

圖由邊的集合及頂點的集合組成。