資料庫系統的實現中採用了哪些常用的數據結構？

01-06

我僅僅知道資料庫系統通常使用B樹來提高訪問輔助存儲設備設備上的性能。

在資料庫里，使用的數據結構不多，但是每一個對技術要求都較高(起碼是工業級的)，說幾個跟存儲引擎相關的:

1. 緩存使用linked-list實現LRU: https://github.com/BohuTANG/nessDB/blob/master/cache/cache.c#L30

2. 索引使用b-tree結構(Fractal-Tree): https://github.com/BohuTANG/nessDB/blob/master/tree/buftree.c

3. 事務並發使用基於binary-tree的locktree: https://github.com/XeLabs/ft-index/blob/master/locktree/locktree.cc

4. MVCC使用stack結構實現嵌套事務版本控制: https://github.com/BohuTANG/nessDB/blob/4c36de92ef238bf9449993e6b3b5c09994860af3/tree/lmb.h#L20

5. 最重要的是要有一個快速的、並發友好的排序結構(vector): https://github.com/BohuTANG/nessDB/blob/master/util/pma.c

6. ConcurrentHashMap用於LRU

https://github.com/BohuTANG/nessDB/blob/master/util/xtable.c

謝邀

之前造的輪子完全沒用標準庫的容器，所有的都自己來，主要是考慮性能、內存管理優化和高並發場景下的無鎖設計。其實基本結構也就是鏈表和數組，拼出來一些複雜結構。

1. 內存池是一大類，比如多次變長申請一次性全釋放的pageArena，帶線程局部緩存的定長對象池，基於引用計數的變長內存池

2. hashmap/hashset，用法跟標準庫差不多，允許外部傳入內存池，桶級別的鎖，支持自動平滑無鎖擴容

3. 無鎖b+tree，其實分裂時也有很小的臨界區，不過百萬級的性能也很好了

4. 無鎖定長queue，基於它可以實現無鎖對象池和內存池，無鎖線程隊列

5. 自己造的vector，初始化小塊的內存直接內嵌vector內，避免每次動態申請

6. 全局計數器，主要是用線程緩存避免每次都修改全局計數器

7. 使用futex優化的threadqueue，降低喚醒開銷，將futex加在每個item上以降低消費者衝突的隊列

8. 無鎖滑動窗口，用來並發執行和結果排序的

9. 無鎖緩存，lru鏈表鎖衝突太大，後來改用數組加堆排序來優化，並使用定長塊來管理內存，避免碎片，並且統一全局各類緩存在一起，按優先順序相互擠占。使用引用計數管理內存

10. 用定長數組實現的無鎖事務列表，支持安全的無鎖遍歷

11. 類似內核頁表的不定長數組，可自動擴容

12. 避免aba問題的內存管理，參考這篇https://zhuanlan.zhihu.com/p/20832611

大概就想起來這些，後面想起來再補充

其他幾個答案說的只是索引，實際上一個資料庫存儲系統中除了索引還有很多重要環節。這個剛好了解一些，一個資料庫存儲引擎，從底層到高層，依次可能用到：

堆（外存存儲記錄的實體）：定長頁和變長頁。定長頁使用記錄長度和下標可以定位到內容，變長頁頭部和記錄是反向存儲的，根據記錄下標可以定位到記錄頭，根據記錄頭定位到記錄存儲。
索引（外存存儲索引的實體）：B+樹
內存記錄緩存：分級的內存池，每塊記錄空間的大小固定。採用LRU或者近似淘汰演算法，非同步將不常用頁面刷出到索引和堆。（並非所有資料庫都有這一層）

猜測啊

鏈表

哈希表

b樹

應該都是必須滴

傳統資料庫系統主要是B+樹，NOSQL基本是hash

索引用的 B+ tree ，理論上還有散列的，實際上我沒用過不知道，mysql里innoDB和myISAM這兩個存儲引擎用的都是 B+ tree。聽說ORACLE用的 B tree 。關係型資料庫應該有用的hash + 鏈表的方式組織數據。書上說還有什麼網狀資料庫，層次資料庫的，用的樹和圖

傳統的關係型資料庫用到了B tree及其一系列變種,hash表

存儲上關係庫底層b+樹存儲數據或者數據根節點（保證迅速定位到數據），根據不同數據類型再延伸另外的數據結構（保證迅速訪問到數據本身）；執行器里各種鏈表，各種樹/圖，hash啊什麼的，基本書上能看到的數據結構在大型通用資料庫里都有利用到

Redis：hashtable，skiplist，linklist……可以去讀一讀《redis設計與實現》

參考《database system implementation》second edition。第十四章，索引結構，索引結構本身就是一種數據結構，資料庫磁碟里採用B+tree索引，另外，還有稠密索引，稀疏索引，輔助索引，哈希表，和點陣圖索引。