赤と黒の木、B(+)の木、ジャンプテーブル、AVLなどのデータ構造、応用シーンと分析、およびいくつかの英語の略語

ネットでいくつかの材料を勉強しました.
この記事:https://www.zhihu.com/question/30527705

AVL :          。             。windows             AVL 

   :     ，    C++ STL 。map set         。     STL map     RBtree,      unordered_map,   hash。

B/B+                    

Trie     ，            

------

AVL           ，        ，                          ，         ，
                          。  ，             ，          ，AVL       。

          ，         STL，  
epoll       ，         
nginx ，      timer 
Java TreeMap  
   linux    Completely Fair Scheduler,           

B B+                  ，  Mysql：B-Tree Index in MySql

trie              ，            ，      ，         
    IP  ，      ，       trie

------

  ：Redis      ，                （         -   Key,   value           ）。

  ，   skiplist？  ziplist。ziplist redis            （       ），   hash       （       ），
                              （redis       ，       ）。        。

 server ，             ，           （          ）。
        ，              ，              ，
       ，              ，         ，                ，
           ，        ，            。         。
      skiplist       ，                   rebalance   ，                   ，
 skiplist            ，          ，              。

さらにRedisの著者らが説明したホップテーブルの使用理由は、

       ，      skiplist The Skip list

There are a few reasons:
1) They are not very memory intensive. It's up to you basically. 
Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive 
than btrees.
 ：           （          ），       ，            ，             。

2) A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list.
 With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
 ：redis       ，             ，       。         （cache locality）       。

3) They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch 
(already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.
 ：    。zrank     O(log(N)).

About the Append Only durability & speed, I don't think it is a good idea to optimize Redis at cost of more code 
and more complexity for a use case that IMHO should be rare for the Redis target (fsync() at every command). 
Almost no one is using this feature even with ACID SQL databases, as the performance hint is big anyway.

About threads: our experience shows that Redis is mostly I/O bound. I'm using threads to serve things from Virtual Memory. 
The long term solution to exploit all the cores, assuming your link is so fast that you can saturate a single core, 
is running multiple instances of Redis (no locks, almost fully scalable linearly with number of cores), 
and using the "Redis Cluster" solution that I plan to develop in the future.

上の文章にはいくつかの英語の略語があり、以下のように整理されています.

imho， imo（in my humble opinion， in my opinion）：    ，     。

idk（I don’t know）：    。

rofl（rolling on the floor laughing）：      。

roflmao（rolling on the floor laughing my ass of）：       ，          。

sth（something）：    。

nth（nothing）：     。

plz（please）： 。please    z  ，         plz。

thx（thanks）：  。      ，thanks   ks     X  。

赤黒樹とB(+)樹工程の実現の比較:

                 ，                 b+      ，     node    kv，                  ，
           ，     ，          ，    node              ，       。

 b+     node    kv，node                  ，       container，             ，
       ，          lockfree，  node   kv   cpu cache     ，                  b+ 。

  b  b+ ，btree      b+    value，        ，node  ，    cpu cache      b+  。
      ，b+      （          ）           （        ），          b+            。

それぞれの特徴特徴の角度から、各種データ構造の応用シーンを分析する.

   ，AVL             。

AVL ：     ，                    ，          1，                  ，        （     1），
                          。            。      AVL              ，       。

   ：     ，                             ，               2 ，        。
            AVL   ，            。     ，                     AVL。
（                ，   “   redis     (skiplist)      red-black？”）

B ，B+ ：        ，      ，          ，   ，           ，
     IO      ，                        IO           。
B+  B     ， n         n    ，          ，     ，          。         。

Trie ：
       ，      ，        。                 。
                 ，                 （   ）。
    
   (prefix tree)，   (suffix tree)，radix tree(patricia tree, compact prefix tree)，crit-bit tree（        ），
      double array trie。
           
   ：       ，     ，      ，          。
   ：     s1 s2 ，   s1 s2      ，   s1,s2      ，     。
radix tree：linux  ，nginx。

赤と黒の木の紹介はこの2つの文章を見ることができます:史上最もはっきりした赤と黒の木の説明(上)+(下)
http://mt.sohu.com/20161014/n470317653.shtml
http://mt.sohu.com/20161018/n470610910.shtml

            ，           ，                     。
        ：
       ，          ；
        ，           。              ：  （Rotate Left），  （RotateRight）

  ，       ，           ：1.         ，2.         。

別の文書では、文字列に関連する様々なアルゴリズムと、接頭辞ツリー接尾辞ツリーなどの様々なツリーを含む様々なデータ構造を分析する.