⑴ 什麼是key value 存儲
key是關鍵字、value是值。
key-value分布式存儲系統查詢速度快、存放數據量大、支持高並發，非常適合通過主鍵進行查詢，但不能進行復雜的條件查詢。
Key-value資料庫是一種以鍵值對存儲數據的一種資料庫，類似Java中的map。可以將整個資料庫理解為一個大的map，每個鍵都會對應一個唯一的值
(1)存儲查詢都快得數據結構擴展閱讀：
由於key-value的鍵值對特性，被廣泛應用鍵值對資料庫中，如redis、memchaced，查詢速度快、存放數據量大、支持高並發，非常適合通過主鍵進行查詢，但不能進行復雜的條件查詢。
key-value型內存資料庫還具有以下特性：
1、亞毫秒級延時。
2、語法簡單，易用性強。
3、支持集群方式水平擴展。
4、支持哈希、列表、集合、有序集合等復雜的數據結構。有更多的應用場景
⑵ 常用數據結構有哪些
數據結構分為8類有：數組、棧、隊列、鏈表、樹、散列表、堆、圖。數據結構是指相互之間存在著一種或多種關系的數據元素的集合和該集合中數據元素之間的關系組成 。
1、數組
數組是可以再內存中連續存儲多個元素的結構，在內存中的分配也是連續的，數組中的元素通過數組下標進行訪問，數組下標從0開始。例如下面這段代碼就是將數組的第一個元素賦值為 1。
2、棧
棧是一種特殊的線性表，僅能在線性表的一端操作，棧頂允許操作，棧底不允許操作。 棧的特點是：先進後出，或者說是後進先出，從棧頂放入元素的操作叫入棧，取出元素叫出棧。
3、隊列
隊列與棧一樣，也是一種線性表，不同的是，隊列可以在一端添加元素，在另一端取出元素，也就是：先進先出。從一端放入元素的操作稱為入隊，取出元素為出隊。
4、鏈表
鏈表是物理存儲單元上非連續的、非順序的存儲結構，數據元素的邏輯順序是通過鏈表的指針地址實現，每個元素包含兩個結點，一個是存儲元素的數據域 (內存空間)，另一個是指向下一個結點地址的指針域。根據指針的指向，鏈表能形成不同的結構，例如單鏈表，雙向鏈表，循環鏈表等。
5、樹
樹是一種數據結構，它是由n（n>=1）個有限節點組成一個具有層次關系的集合。把它叫做 「樹」 是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。
6、散列表
散列表，也叫哈希表，是根據關鍵碼和值 (key和value) 直接進行訪問的數據結構，通過key和value來映射到集合中的一個位置，這樣就可以很快找到集合中的對應元素。
7、堆
堆是一種比較特殊的數據結構，可以被看做一棵樹的數組對象，具有以下的性質：堆中某個節點的值總是不大於或不小於其父節點的值；堆總是一棵完全二叉樹。將根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆。常見的堆有二叉堆、斐波那契堆等。
8、圖
圖是由結點的有窮集合V和邊的集合E組成。其中，為了與樹形結構加以區別，在圖結構中常常將結點稱為頂點，邊是頂點的有序偶對，若兩個頂點之間存在一條邊，就表示這兩個頂點具有相鄰關系。
⑶ 使用什麼數據結構可以快速遍歷查找的所需數據
最快的肯定是
散列
（也叫哈希），其次是
樹形結構
，再其次是索引
順序結構
（也叫作分塊）
⑷ 資料庫系統的實現中採用了哪些常用的數據結構
資料庫索引文件採用數據結構概述： 1、非主鍵索引需要在數據表本身的存儲空間外額外開銷存儲空間，所以在更新的時候可能不僅要更新數據表本身，還要更新非主鍵索引，更新內容更多了，所以導致速度降低。反過來，如果數據表中的數據按照主鍵索引的順序存儲，更新的時候就沒有額外的開銷。 非主鍵索引對提高查詢速度來講，主要的方面是：檢索的條件(where...)如果命中對應的非主鍵索引的話，就不需要對數據表做全表掃描，效率肯定是大大提高。（索引的創建和使用是資料庫設計和優化的重要部分，是一個資料庫程序員的必修課，不同資料庫系統的語法不同，但是原理基本相同）; 2、如果檢索結果的欄位包含在非主鍵索引中，即使對非主鍵索引做全掃描，也比對整表欄位做全掃描快，因為只有非主鍵索引本身的數據需要從存儲設備調入內存，節約了IO時間。 3、不過一般說索引對查詢速度的影響，主要指第一種情況。 關於資料庫索引的數據結構，大多數資料庫都是採用B樹。可參照文章： 非主鍵索引需要在數據表本身的存儲空間外額外開銷存儲空間，所以在更新的時候可能不僅要更新數據表本身，還要更新非主鍵索引，更新內容更多了，所以導致速度降低。反過來，如果數據表中的數據按照主鍵索引的順序存儲，更新的時候就沒有額外的開銷。 非主鍵索引對提高查詢速度來講，主要的方面是：檢索的條件(where...)如果命中對應的非主鍵索引的話，就不需要對數據表做全表掃描，效率肯定是大大提高。（索引的創建和使用是資料庫設計和優化的重要部分，是一個資料庫程序員的必修課，不同資料庫系統的語法不同，但是原理基本相同）; 另一方面，也有如下的可能：如果檢索結果的欄位包含在非主鍵索引中，即使對非主鍵索引做全掃描，也比對整表欄位做全掃描快，因為只有非主鍵索引本身的數據需要從存儲設備調入內存，節約了IO時間。 不過一般說索引對查詢速度的影響，主要指第一種情況。
⑸ 可持久化數據結構
最近在刷MIT 6.851，記錄下筆記。
可持久化數據結構就是能存儲、查詢數據的歷史版本的數據結構。
http://hypirion.com/musings/understanding-persistent-vector-pt-1
https://www.geeksforgeeks.org/persistent-data-structures/?ref=lbp
可持久化數據結構簡介
MIT 6.854j-advanced-algorithms
很贊！！可惜沒video。
Making Data Structures Persistent
太長沒看
總結了下大致包括如下領域應用：
並發事務的原子性（便於Rollback）、隔離性。
https://io-meter.com/2016/09/03/Functional-Go-persist-datastructure-intro/
同上。
便於實現diff,rollback
可持久化數據結構最初設計出來的目的是為了在高維查詢中降維，把其中一個維度當做時間，用可持久化數據結構處理效率更高
可以看下MIT 6.851老師的介紹。
這種思想在高維處理中很常見，比如求二維range sum query時候，把其中一個維度當時間、拿來做掃描線也是這種降維思路（見《演算法競賽進階指南》）：
可持久化數據結構簡介
自己輪一個.net可持久化庫 Persistent Data Structures 下面有討論use case
中文翻譯見 可持久化數據結構
Functional Go: 持久化數據結構簡介
這部分可以看6.851視頻
6.851把鏈式數據結構的模型叫pointer machine model。對於基於pointer machine model的數據結構，有沒有通用的方法將他們改造成persistent？
note see https://ocw.mit.e/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/lecture-notes/persistent.pdf
video see https://www.bilibili.com/video/BV1iE411n7yJ
O(1)寫，讀時對於每個點都要執行O(logm)的查詢。假設一次查詢要讀v個點，時間復雜度O(vlogm)
所以對寫友好，對讀不友好
看到這里有個問題：每個點的history放hashmap里不就行了？讀時也只需要O(1)的查找
但這樣做的話，hashmap不支持ceil操作，因此要支持ceil沒辦法只能用有序結構、log級別查詢
（這里的假設是有個全局時間戳，而不是每個key對應一個自己的自增時間戳）
個人理解，想做可持久化key/value Map的話即可按這種方法，每個key對應的entry存放所有歷史值，這也可以看成是鄰接表。
說白了就是寫時分裂節點，從root開始分裂到要寫的點。將所有version的root存到字典里
上面兩個要麼對寫不好，要麼對讀不好，能否兼得？
難以置信，說白了就是給path ing方法中每個node加一個log cache，最後算出來的寫時amortized time complexity就是O(1)了。
What about non-tree data structures？
平衡樹怎麼處理？
平衡樹要旋轉，想想就感覺很難改造成持久化。6.854課件講的很粗沒懂。 演算法競賽中常用的可持久化平衡樹一般就是 可持久化無旋轉 Treap ，省去了旋轉可持久化的復雜。
a. fat nodes
每個點存的log從version queue變成version tree,查詢每個點時要從樹中找到最近祖先
b. path ing
沒區別
c. modification box
怎麼找根節點？
i. pointer per version，可能多個pointer指向一個root
ii.存root tree,查詢時先找最近祖先
怎麼修改old version
i. 修改時放box,滿了就分裂出來一個新節點
但這樣有問題：分裂出來的還是滿的，如果整條鏈都是滿的，每次修改復制全部，下次修改還得復制全部。而且這樣還不好存root，比如最右邊圖，代表0的root有倆
ii. 修改時放box,滿了就分裂出來一個新節點，但分裂時自動apply有用的log、丟棄沒用的log
What about non-tree data structures？
6.851有講，分裂成兩個節點，log分成兩部分，新節點拿一個子樹的log，新節點apply log直到自己的子樹，每部分丟棄自己用不到的。
6.851講了 太復雜沒聽懂。
網上關於可持久化數據結構的優質資料都是演算法競賽的，因此收集總結了下競賽常用的。看了下基本都是partial persistent,有的是fully persistent,都沒用到modification box技術。
https://github.com/Misaka233/algorithm/blob/master/%E9%99%88%E7%AB%8B%E6%9D%B0%EF%BC%9A%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%A0%94%E7%A9%B6.pdf
https://www.bilibili.com/video/BV1C4411u7rK?p=1
https://www.geeksforgeeks.org/persistent-trie-set-1-introction/
和可持久化線段樹類似的方法，基於path 實現partial persistence。
問題是每個點在拷貝時都要復制O(R)個指針，插入的時間復雜度為O(len*R)
查詢時先從字典（數組/哈希表）里找到指定version的root，然後訪問，O(len)
在競賽中常用的是可持久化01字典樹，比如xor問題，見 https://oi-wiki.org/ds/persistent-trie/ ，沒看懂
演算法競賽中常用的可持久化平衡樹一般就是 可持久化無旋轉 Treap ，省去了旋轉可持久化的復雜。
【AgOHの數據結構】可持久化數組
https://www.luogu.com.cn/problem/P3919
方案：
a. fat nodes
每個節點放所有歷史，查詢時在所有歷史版本中找最近祖先版本
b. path ing
存到可持久化線段樹里。
為什麼好好的線性結構要樹化？直覺上理解，是為了分裂新版本時減少指針復制。
如果是稀疏數組，樸素方法太浪費空間了，可以基於動態開點來優化空間存儲，見 https://io-meter.com/2016/11/06/functional-go-intro-to-hamt/
【AgOHの數據結構】可持久化並查集
並查集基於數組，可持久化並查集就基於可持久化數組。可持久化數組用可持久化線段樹實現，因此可持久化並查集用可持久化線段樹實現
《 可持久化數據結構研究 》
不過文中寫的太簡略了，個人推測的維護方法為：
https://io-meter.com/2016/09/03/Functional-Go-persist-datastructure-intro/
討論支持如下操作的抽象數據結構(ADT)如何可持久化：
a. 基於普通數組
只能 on write
b. 基於可持久化數組/可持久化線段樹
問題是怎麼處理新增節點、刪除節點？得想辦法魔改線段樹
c. 可持久化鏈表
d. 可持久化塊狀鏈表
e. 可持久化平衡樹
f. 文中提到的vector trie
名字挺騷的沒反應過來，看了一會發現：這玩意就是可持久化數組（可持久化線段樹），只不過是多叉樹，叫「可持久化多叉線段樹」比較形象。文章也沒提怎麼處理新增節點、刪除節點。
persistent-hash-table-implementation
a. 可持久化平衡樹
b. 還用hashmap，但是每個entry改造成fat node（存放所有log)，查詢時先找到entry，再在所有log 中找最近祖先版本
c. 可持久化數組。
考慮到HashMap本來就能只用一個數組實現（解決沖突時用open addressing方法，不用Chaining），那麼實現了可持久化數組就相當於實現了可持久化HashMap
d. Hash_trie
hash(key)的值存在trie里,value放到trie的葉子節點。優化版本包括 Hash array mapped tries and Ctries
HAMT這名字起的很奇怪。原理就是塊狀hash trie（所謂塊狀是我自己起的名，指每個節點區分兒子時不是單純的比較某1位，而是比較某2位甚至多位）（或者理解成hash trie+動態開點多叉線段樹也行）（反正就是bitwise hash trie加上一堆優化，懶得記就記hash trie就行了，真要自己實現的時候這些優化trick也能想到）
文中講hamt的碰撞處理有點扯，個人理解可以chaining，可以open addressing。細節沒深究，可以看 論文 和 討論 。按作者的意思AMT是之前他提出的一種Trie的優化，比Tenary search trie要好。
https://www.cnblogs.com/tedzhao/archive/2008/11/12/1332112.html
// TOOD
https://www.cnblogs.com/zinthos/p/3899565.html
Planar Point Location問題見
https://courses.csail.mit.e/6.851/spring12/scribe/lec3.pdf
https://www.bilibili.com/video/BV1iE411n7yJ?p=3
http://acrossthesky.logdown.com/posts/712254-some-basic-data-structures
https://github.com/Misaka233/algorithm/blob/master/%E9%99%88%E7%AB%8B%E6%9D%B0%EF%BC%9A%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%A0%94%E7%A9%B6.pdf
https://download.csdn.net/download/u011808175/6477705
樸素的方法是線段樹套線段樹，以便支持二維RMQ，時間復雜度O(logN*logN）。
個人理解，最優的二維RMQ數據結構應該是用modification box實現的可持久化值域線段樹，O(N)的構造時間、空間，O(logN)的查詢。
如果統計操作具有「區間可加性」、「區間可減性」，那麼該操作二維統計問題可以使用可持久化線段樹。
range minimum query中的min()操作其實不具有區間可減性，但是range minimum query問題可以歸約成range select query問題，進而可以歸約成range count query問題，而count()操作具有區間可加減性，因此也能用可持久化線段樹。
所以我們得到了一類二維統計問題的通用數據結構：對於可歸約成具有「區間可加性」、「區間可減性」統計操作的二維統計問題，可以使用可持久化線段樹存儲，以便支持快速查詢（統計）。
能否找到一類高維統計問題，具有通用的logN級別解？個人理解可以借鑒代數的思想，只要有區間可加減性的都能歸約成K維RMQ問題，用modification box實現的可持久化值域線段樹解決。
// TOOD 只是個人暢想，沒細想。
bigtable(hbase)可以看成外存模型下的可持久化map：
但需要注意的是刪除操作會真的刪掉之前的老版本數據：
其實任何支持前綴匹配的db都能作為可持久化map，你只需要把rowkey設計成"key@@timestamp"即可
http://hbase.apache.org/book.html#reverse.timestamp
⑹ 數據結構中有哪些查找，他們分別適用於查詢那種存儲結構
最常見的：
順序查找：適合順序結構和鏈式結構
二分查找：適合順序結構
其他的二叉查找樹、B-樹之類有自己的數據結構
⑺ 用C++如何實現數據的快速查找和存儲
數據通過相應的數據結構存儲，所以查找是在數據結構的基礎上進行。 一般為了保證查找的效率通常使用順序存儲結構，比如數組等可直接通過下標獲取元素的結構。
存儲一般考慮需求，如果後面有大量插入刪除操作則選擇鏈表等結構
望採納