1樓：lxyscls
參考一下CMU15-445，磁碟上的雜湊和記憶體中的雜湊實現上不太一樣，所以不是太適合做磁碟的索引，當然bitcask其實是把雜湊索引放到記憶體裡面。
2樓：
讀：有序的索引功能會豐富很多，比如levelDb可以支援snapshot read，hash的話想來只能做backup了。另外Hash的優勢在於單次訪問IO定址少，而LevelDB的bloom filter對此有所緩解。
寫：兩者都需要背景的合併操作。而hash的寫操作貌似不可以批量進行，不管用disk還是ssd都不能很好利用其特性。所以hash的寫效能應該比較差。
3樓：魯塔弗
涉及到磁碟訪問，都不會用hash這個結構，1.是無法做range查詢，2 從磁碟load很慢，用結構化陣列存，mmap可以秒開
4樓：iseeyou
一般來說，索引本身很大，不可能全部儲存在記憶體中，因此索引往往以索引檔案的形式儲存的磁碟上。這樣的話，索引查詢過程中就要產生磁碟I/O消耗，相對於記憶體訪問，I/O訪問的消耗要高幾個數量級，所以決定索引效能的乙個最重要指標就是在查詢過程中磁碟I/O操作次數的漸進複雜度，換句話說，索引的結構組織要儘量減少查詢過程中磁碟I/O的訪問次數。一般來講，索引有如下幾種資料結構：
1、B+樹索引：mysql的預設索引型別，B+樹的內結點只儲存了key沒有儲存data，節點的出度大，樹的高度小，查詢的磁碟定址次數就少，因此擁有不錯的效能
2、hash索引：hash表的查詢複雜度只有O(1)，索引的檢索可以一次定位，不像B+Tree 索引需要從根節點到枝節點，但不支援範圍查詢，另外在有大量重複鍵值或者資料量非常大的情況下，雜湊索引的效率也是極低的，因為存在所謂的雜湊碰撞問題。
3、FULLTEXT索引：全文索引，lucene、elasticsearch的預設索引型別，也叫反向索引、倒排索引，即根據關鍵字來找到文件
4、空間索引：mongodb和MySQL 5.7之後的版本都支援空間索引，用於對GIS資料型別的索引，比如根據自己所在位置查詢來查詢附近50公尺的POI（point of interest）
5、位圖索引：位圖索引是一種特殊的索引，適用範圍比較小，只適用於字段值固定並且值的種類很少的情況，比如性別，只能有男和女，或者級別，狀態等
6、LSM：Log Structured-Merge Tree,當前許多產品都在使用，比如HBase, Cassandra, LevelDB, SQLite。LSM通過消去隨機的本地更新操作，把磁碟隨機寫操作變為順序寫操作，從而得到更好的寫操作吞吐量。
LSM樹的設計思想非常樸素，將對資料的修改增量保持在記憶體中，達到指定的大小限制後將這些修改操作批量寫入磁碟。檔案是不可修改的，他們永遠不會被更新，新的更新操作只會寫到新的檔案中。讀操作會依次從最新的檔案查詢，通過週期性的合併這些檔案來減少檔案個數。
所以寫入效能大大提公升，讀取時可能需要先看是否命中記憶體，否則需要訪問較多的磁碟檔案。
綜上，LSM索引相比雜湊索引能夠大幅提高寫效能，資料量非常大的情況下因為雜湊碰撞雜湊索引的效率低
5樓：Thomas Lau
上層需求決定底層資料結構的選型，只是一種非常技巧的解決方案罷了，當然也可能會有比他更好的資料結構。
哪來的為什麼，不要看到表象就認為表象是問題。再說市面上不缺hash。
6樓：
雜湊是非常快的索引結構，做資料庫的都想用它，簡單啊，二元組一打即可，O(1)IO複雜度，但是碰到range scan就歇菜了，如果不是非常大且不需區間查詢，當然可以hash了
7樓：褲褲
1、levelDB索引不是LSM，是Sorted List，類似平衡樹。LSM（Log-Structured-Merge Tree）是levelDB的儲存策略或者說檔案結構策略，即：
2、為什麼levelDB索引是Sorted List不是Hash
levelDB是key-value資料庫，本身就是hash，再用hash索引沒有意義，Sorted List實現很巧妙，比二分查詢更高效，讀寫都是。另外Sorted list更適合遍歷
8樓：鬍子
看LevelDB對自己的介紹和定義咯，提供乙個有序的KV資料儲存，Hash索引顯然不能滿足要求啊，Hash之後的hashkey之間沒法比較，只能判斷是否相等。 所以要做範圍搜尋，排序，等操作。至於LSM為啥能滿足要求請看 LSM 演算法的原理是什麼？
- 知乎
9樓：
in-memory索引用的skiplist，持久化借鑑了lsm思想，用的自己的sst格式。lsm解決的不是索引問題，而是可以直接盲寫，提高寫效能。
10樓：Gavin Wu
主要使用場景是寫多讀少，同時KV命中不是依託維護乙個全域性的HASH表，而是部分維護了乙個跳躍性的TREEMAP，所以杜操作可能會回溯若干個SSTable。
而全域性雜湊表維護成本大，且易形成瓶頸，而做成區域性有序索引可以一定情況下滿足檢索效率
11樓：dong
不同的資料結構，不同的理念，產生不同的表現。
大部分不同，樓上已經說明，下面就某些地方給出更深入的對比從索引的效率來看，leveldb與bitcask（雜湊索引的代表）都可以做到讀取1條記錄訪問1次磁碟（leveldb平均在1.07次磁碟讀取），但leveldb採用的bloomfilter僅僅需要占用10bit/記錄，遠遠低於bitcask。
從額外磁碟空間來看，leveldb如果採用rocksdb中的動態層級增長，那麼額外空間約0.11，而bitcask嚴重依賴於合併前的資料寫入量。
12樓：drdr xp
往磁碟上sync一下hash表應該很痛苦吧…
我覺得lsm和btree還有的比。
lsm和fractal tree本質一樣，都是有利於寫多的持久儲存。
13樓：fleuria
與 bitcask 做對比可能比較好：
Bitcask 是乙個雜湊，只能存無序資料；Leveldb 可以儲有序資料，有序資料總是相鄰地儲存，應用程式可以利用儲存的區域性性；
Bitcask 的一次檢索只觸發一次磁碟讀，Leveldb 的 Bad Case 會有少量多次讀取（每次磁碟讀跳乙個 Level），但是可以快取索引；
Bitcask 將索引整個放在記憶體裡，鍵過多時，會佔據過多記憶體；Leveldb 中每個 Level 乙個 Manifest 用於索引每個 SSTable 的範圍，佔據的記憶體較小，節約的記憶體可以更多地放快取；
Leveldb 將資料按 Level 下的 SSTable 合併，相比 Bitcask 更 Graceful；
Bitcask 的區域性寫會導致大量冗餘寫，不適合儲存頻繁修改的資料；這同樣也是 Leveldb 的弱項（相比 BTree ），但是頻繁修改的熱資料，有 MemTable 可以扛一下；
c 用乙個方法讀取資料庫資料到不同Model類的例項，如何用泛型實現？
如果只是一句 SQL 泛型約束 執行 泛型類例項這樣的需求有很多方法，說來說去也就三個主要步驟 一.執行 SQL 語句，返回 DataReader 或者 DataTable，這兩個都可以使用列名訪問到資料。二.選擇不同的方式建立 Model 與資料庫表的對映關係，最簡單就是 PropertyName...
怎麼實現乙個簡單的資料庫系統？
劉浩浩 這種類似的東西，最重要的是一定要看過已經有的開源實現的原始碼，從頭到尾搞懂別人的思路。我自己寫過基於UDP的可靠協議，用go寫的，開始寫之前看了各種他人的原始碼和一些已有的實現，感覺受益匪淺，後面寫起來感覺前期的調研是很重要的。因此建議，先看懂乙個完整的實現，不需要mysql這樣的大東西，看...
如何修改乙個已存在的資料庫名稱？
愛可生 被取消的命令MySQL 之前提供了乙個 rename database db old to db new 的命令來直接對資料庫改名，可能由於實現的功能不完備 比如，這條命令可能是乙個超大的事務，或者是由於之前的表很多還是 MyISAM 等 後來的版本直接取消了這條命令。更改資料庫名大致上有以...