The [Deep Dive -> B-Tree] section may contains incorrect contents

[LENSHOOD]

Change Request

The B-Tree picture and descriptions related to the pic maybe incorrect. Location: Deep Dive -> Key-value engine -> B-Tree vs LSM-Tree

Describe the problem / Suggest an improvement/fix

---

1. This picture is not (typically) a B-Tree nor B+Tree or B*-Tree

   • B-Tree cannot contain duplicated keys (like 15/25/30 in the pic)
   • B+Tree contains pointers between the leaf nodes
   • B*-Tree contains pointers between internal siblings

   Maybe is better to post a standard B-Tree or just modify current pic to a B+Tree (since the below content mostly use B+Tree as example).

---

Figure 1. The root node is shown at the top of the tree, and in this case happens to contain a single pivot (20), indicating that records with key k where k ≤ 20 are stored in the first child, and records with key k where k > 20 are stored in the second child. The first child contains two pivot keys (11 and 15), indicating that records with key k where k ≤ 11 is stored in the first child, those with 11 < k ≤ 15 are stored in the second child, and those with k > 15 are stored in the third child. The leftmost leaf node contains three values (3, 5, and 7).

2. Ignore the picture's issue, the quote section are also contains error:
   • k ≤ 20 should be k < 20
   • k ≤ 11 should be k < 11
   • 11 < k ≤ 15 should be 11 ≤ k < 15
   • k > 15 should be k ≥ 15

• Relevant URL(s): https://tikv.org/deep-dive/key-value-engine/b-tree-vs-lsm/