redis設計了SDS這一數據結構來表示字符串而不是使用c語言的字符串:字符數組
那么redis為什么要大費周章自己設計字符串呢?
答案是C語言字符串有缺陷
1.獲取字符串長度,需要遍歷字符數組,時間復雜度是O(N)
2.字符串結尾以"\0"表示,因此字符串內容本身不能包含"\0",因此不能保存二進制數據
3.字符串操作函數不安全,可能會造成緩沖區溢出(這個你一定知道)
我們一一詳細介紹這些c語言字符串的缺陷
1.獲取字符串長度性能低
由于c語言字符串就是一個以’\0’結尾的字符數組,當你需要一個字符串的長度時,你可能會調用strlen函數,那么這個函數是如何獲取字符串的長度的呢?
strlen會遍歷整個字符數組,一直遇到’\0’結束
這個操作的時間復雜度是O(N),對于redis來說代價太大了
redis是怎么解決獲取字符串長度的問題的?
可以看到,對于redis的字符串SDS,不單有保存字符串的數組空間,還有一些額外的成員
len,記錄字符串長度,使得獲取字符串長度的時間復雜度降到O(1)
2.緩沖區溢出
舉個例?,strcat 函數是可以將兩個字符串拼接在?起。
C 語?的字符串是不會記錄?身的緩沖區??的,所以 strcat 函數假定程序員在執?這個函數時,已經為 dest 分配了?夠多的內存,可以容納 src 字符串中的所有內容,??旦這個假定不成?,就會發?緩沖區 溢出將可能會造成程序運?終?。
Q:redis是如何解決的?
A:SDS的alloc成員,分配給字符數組的空間?度。這樣在修改字符串的時候,可以通過 alloc - len 計算出剩余的 空間??,可以?來判斷空間是否滿?修改需求,如果不滿?的話,就會?動將 SDS 的空間擴展? 執?修改所需的??,然后才執?實際的修改操作,所以使? SDS 既不需要?動修改 SDS 的空間? ?,也不會出現前?所說的緩沖區溢出的問題
3.不能保存二進制數據
這個很好理解,由于’\0’代表字符串結尾,會造成讀入終止,這個限制使得 C 語?的字符串只能保存?本數據,不能保存像圖?、?頻、視頻?化這 樣的?進制數據
推薦學習 https://xxetb.xetslk.com/s/p5Ibb