Etcd是一个分布式键值存储系统，使用B+树作为底层数据结构来实现高效的查找和排序。在Etcd中，每个节点都包含一个索引，用于快速定位到某个键值对所在的位置。
索引
Etcd中的索引是一种将键映射到其所在位置的数据结构。通过索引，Etcd可以快速地定位到一个特定键值对所在的位置，从而提高读写操作的效率。
在Etcd中，索引是通过B+树来实现的。B+树是一种平衡树结构，在插入、删除和查找操作时具有O(log n)复杂度。每个节点都包含多个子节点和对应子节点范围内最大、最小键值及其所指向子节点的指针（或偏移量），这些信息使得查询时只需要遍历数次即可完成搜索。
除了主要用于加速单个Key查找外，在Range查询中也会使用到Index。例如Range查询 /foo 时，客户端请求首先会被路由到集群中任意一个节点上执行本地查询，并返回所有key以/foo为前缀的结果列表及这些结果在整体Key空间内的范围界限信息（即begin和end）。当后续客户端继续向该集群发送带有Range参数请求时，则可以直接利用之前返回的范围信息来快速定位查询范围，并只需要返回该范围内的结果。
B+树
B+树是一种平衡树，由Rudolf Bayer和Edward M. McCreight于1972年提出。它是B树的一种改进版本，在应用中广泛使用，如数据库、文件系统等。
在B+树中，所有关键字都保存在叶子节点上，而非叶子节点上只保存关键字的索引。同时，每个叶子节点之间都有指针相连，形成一个链表结构，方便进行区间查找操作。此外，在B+树中所有记录按照关键字大小顺序存放在同一层次的叶子节点上，并且任何两个相邻的叶子节点之间距离相等。
与红黑树和AVL树不同的是，在B+树中每个非终端节点不仅包含关键字值及其所对应的数据块地址或指针，还包含了若干个分支节点所代表区间内最大、最小键值以及这些分支对应的地址或偏移量。这样可以使得单次访问时覆盖到更多数据块，并减少IO读写操作次数。
总体来说，B+树通过使用索引实现快速定位到某个键值对所在位置，并通过合理划分区间和链表结构等方式，优化了范围查询和遍历操作的效率。因此，在Etcd这种高性能键值存储系统中使用B+树作为底层数据结构，可以大幅提升系统的读写效率。
![/data # iw --debug dev wlan0 connect -w "lucky-5g" auth open key 0:1234567890
Usage: iw [options] dev connect [-w] [] [] [auth open|shared] [key 0:abcde d:1:6162636465] [mfp:req/opt/no]
Join the network with ...](https://linuxcpp.0voice.com/zb_users/upload/2023/05/202305162239148267954.png)
![驱动代码
void kalRxTaskletSchedule(struct GLUE_INFO *pr)
{
static unsigned int num = 0;
tasklet_hi_schedule(&pr->rRxTask[(num++)%NR_CPUS]);
// tasklet_hi_schedule(&pr->rRxTask);
DBGLOG(HAL, ERROR,](https://linuxcpp.0voice.com/zb_users/upload/2023/05/202305162226144313964.png)
