面试题答案
一键面试1. MemStore数据结构组成
HBase的MemStore主要由**跳表（SkipList）和内存块（Memory Block）**组成。
跳表（SkipList）
- 组织方式：跳表是一种有序的数据结构，它以多层链表的形式组织数据。每一层链表都是一个有序的链表，上层链表是下层链表的子集。通过随机化的方式决定每个节点在高层链表中的出现概率，通常概率为1/2或1/4等。
- 存储数据：跳表中的每个节点存储着键值对（KeyValue），键值对按照RowKey排序。RowKey是HBase中数据的重要标识，决定了数据在表中的存储顺序。
- 作用：跳表为MemStore提供了快速的查找、插入和删除操作。由于其多层结构，可以快速定位到目标数据所在的范围，大大提高了查询效率。例如，在查找一个RowKey对应的KeyValue时，可以从高层链表开始查找，逐步向下层链表定位，减少查找的时间复杂度，平均时间复杂度为O(log n)。
内存块（Memory Block）
- 组织方式：内存块是连续的内存区域，用于批量存储KeyValue数据。MemStore会将多个KeyValue按照一定规则组织成内存块。当内存块达到一定大小（通常由配置参数决定）时，会进行切分或合并操作。
- 存储数据：内存块中顺序存储着KeyValue，这些KeyValue按照RowKey顺序排列。这样的顺序存储有助于后续的排序和刷写操作。
- 作用：内存块的批量存储方式减少了内存碎片，提高了内存的使用效率。同时，顺序存储的数据在刷写到磁盘时，可以利用顺序I/O的优势，提高刷写速度。例如，当MemStore需要将数据刷写到磁盘形成HFile时，内存块中的顺序数据可以直接按照顺序写入磁盘，减少磁盘寻道时间。
2. MemStore运行过程中不同数据结构的作用
写入操作
- 跳表：当有新的KeyValue写入MemStore时，首先会插入到跳表中。跳表的快速插入特性保证了写入操作的高效性，能够快速定位到合适的插入位置，维持数据的有序性。
- 内存块：随着新数据的不断插入，当内存块达到一定大小后，会进行切分或合并。这有助于管理内存使用，同时确保内存块中的数据是顺序存储的，为后续刷写操作做准备。
读取操作
- 跳表：查询操作主要依赖跳表。由于跳表是有序的，通过二分查找的思想，可以快速定位到目标RowKey对应的KeyValue。例如，在查询某个RowKey的数据时，跳表能够迅速缩小查找范围，提高查询效率。
- 内存块：虽然内存块本身不直接参与查询的核心逻辑，但内存块中顺序存储的数据有助于跳表快速定位到具体的数据范围。因为跳表的节点可能指向内存块中的某个位置，通过内存块的顺序结构可以快速遍历相关的数据。
刷写操作
- 跳表：在刷写操作前，跳表中的数据需要按照一定顺序组织起来，以便写入磁盘形成HFile。跳表的有序结构使得数据可以直接按照顺序输出，为刷写提供了有序的数据来源。
- 内存块：内存块中的顺序数据可以直接批量写入磁盘，利用顺序I/O的优势，提高刷写效率。多个内存块的数据会按照顺序合并，最终形成一个有序的HFile存储在HDFS上。