Phoenix介绍

1.什么是Phoenix

Phoenix是一个HBase的开源SQL引擎。你可以使用标准的JDBC API代替HBase客户端API来创建表，插入数据，查询你的HBase数据。

2.Phoenix底层原理

Phoenix框架将命令行上键入的sql语句翻译成hbase指令，然后hbase用翻译好的指令去操作集群，执行完之后给客户端反馈结果。

3.安装部署

• 需要先安装好hbase集群，phoenix只是一个工具，只需要在一台机器上安装就可以了，这里我们选择node02服务器来进行安装一台即可

1、下载安装包

• 从对应的地址下载：

  http://www.apache.org/dyn/closer.lua/phoenix/phoenix-5.1.1/phoenix-hbase-2.2-5.1.1-bin.tar.gz

• 这里我们使用的是

  • phoenix-hbase-2.2-5.1.1-bin.tar.gz

2、上传解压

• 将安装包上传到node02服务器的/kkb/soft路径下，然后进行解压

cd /kkb/soft/
tar -zxf phoenix-hbase-2.2-5.1.1-bin.tar.gz   -C /kkb/install/

3.安装

cd /kkb/install/phoenix-hbase-2.2-5.1.1-bin
cp -a phoenix-server-hbase-2.2-5.1.1.jar ../hbase-2.2.6/lib/

mv bin/hbase-site.xml  bin/hbase-site.xml.init

cp $HBASE_HOME/conf/hbase-site.xml ./bin
cp $HADOOP_HOME/etc/hadoop/hdfs-site.xml ./bin

4.配置环境变量

sudo vim /etc/profile

#phoenix
export PHOENIX_HOME=/kkb/install/phoenix-hbase-2.2-5.1.1-bin
export PHOENIX_CLASSPATH=$PHOENIX_HOME
export PATH=$PATH:$PHOENIX_HOME/bin

source /etc/profile

5.重启hbase集群

• 记得要先启动hadoop集群、zookeeper集群

• ==node01执行==以下命令来重启hbase的集群

cd /kkb/install/hbase-2.2.6
bin/start-hbase.sh
bin/stop-hbase.sh 

4、验证是否成功

• 1、在phoenix/bin下输入命令, 进入到命令行，接下来就可以操作了

  ==node02执行==以下命令，进入phoenix客户端

  cd /kkb/install/phoenix-hbase-2.2-5.1.1-bin/
  bin/sqlline.py node02:2181

5、Phoenix使用

1、 批处理方式

• 1、node02执行以下命令创建user_phoenix.sql文件
  • 内容如下

mkdir -p /kkb/install/phoenixsql
cd /kkb/install/phoenixsql/
vim user_phoenix.sql

create table if not exists user_phoenix (state varchar(10) NOT NULL,  city varchar(20) NOT NULL, population BIGINT  CONSTRAINT my_pk PRIMARY KEY (state, city));

• 2、node02执行以下命令，创建user_phoenix.csv数据文件

cd /kkb/install/phoenixsql/
vim user_phoenix.csv

NY,New York,8143197
CA,Los Angeles,3844829
IL,Chicago,2842518
TX,Houston,2016582
PA,Philadelphia,1463281
AZ,Phoenix,1461575
TX,San Antonio,1256509
CA,San Diego,1255540
TX,Dallas,1213825
CA,San Jose,912332

• 3、创建user_phoenix_query.sql文件

cd /kkb/install/phoenixsql
vim user_phoenix_query.sql

select state as "userState",count(city) as "City Count",sum(population) as "Population Sum" FROM user_phoenix GROUP BY state; 

• 4、执行sql语句

cd /kkb/install/phoenixsql

/kkb/install/phoenix-hbase-2.2-5.1.1-bin/bin/psql.py  node01:2181 user_phoenix.sql user_phoenix.csv  user_phoenix_query.sql

2、 命令行方式

• 执行命令

cd /kkb/install/phoenix-hbase-2.2-5.1.1-bin/
bin/sqlline.py node02:2181

• 退出命令行方式，phoenix的命令都需要一个感叹号

!quit

• 查看phoenix的帮助文档，显示所有命令

0: jdbc:phoenix:node02:2181> !help

2.1表的映射

• 1、建立employee的映射表

  进入hbase客户端，创建一个普通表employee，并且有两个列族 company 和family
  node01执行以下以下命令进入hbase 的shell客户端

  cd /kkb/install/hbase-2.2.6/
  bin/hbase shell
  hbase(main):001:0> create 'employee','company','family'

• 2、数据准备

  put 'employee','row1','company:name','ted'
  put 'employee','row1','company:position','worker'
  put 'employee','row1','family:tel','13600912345'
  put 'employee','row1','family:age','18'
  put 'employee','row2','company:name','michael'
  put 'employee','row2','company:position','manager'
  put 'employee','row2','family:tel','1894225698'
  put 'employee','row2','family:age','20'

• 3、建立hbase到phoenix的映射表

  node02进入到phoenix的客户端，然后创建映射表

  cd /kkb/install/phoenix-hbase-2.2-5.1.1-bin
  bin/sqlline.py node02:2181
  
  CREATE TABLE IF NOT EXISTS "employee" ("no" VARCHAR(10) NOT NULL PRIMARY KEY, "company"."name" VARCHAR(30),"company"."position" VARCHAR(20), "family"."tel" VARCHAR(20), "family"."age" VARCHAR(20)) column_encoded_bytes=0;

  说明

  在建立映射表之前要说明的是，Phoenix是大小写敏感的，并且所有命令都是大写

  如果你建的表名没有用双引号括起来，那么无论你输入的是大写还是小写，建立出来的表名都是大写的

  如果你需要建立出同时包含大写和小写的表名和字段名，请把表名或者字段名用双引号括起来。

• 4、查询映射表数据

0: jdbc:phoenix:node1:2181> select * from "employee";
+-------+----------+-----------+--------------+------+
|  no   |   name   | position  |     tel      | age  |
+-------+----------+-----------+--------------+------+
| row1  | ted      | worker    | 13600912345  | 18   |
| row2  | michael  | manager   | 1894225698   | 20   |
+-------+----------+-----------+--------------+------+

0: jdbc:phoenix:node01:2181> select * from "employee" where "tel" = '13600912345';
+-------+-------+-----------+--------------+------+
|  no   | name  | position  |     tel      | age  |
+-------+-------+-----------+--------------+------+
| row1  | ted   | worker    | 13600912345  | 18   |
+-------+-------+-----------+--------------+------+

3.JDBC

• 创建maven工程并导入jar包

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <parent>
        <artifactId>XZK</artifactId>
        <groupId>org.example</groupId>
        <version>1.0-SNAPSHOT</version>
    </parent>
    <modelVersion>4.0.0</modelVersion>

    <artifactId>phoenixDemo</artifactId>
    <dependencies>
        <dependency>
            <groupId>org.apache.hbase</groupId>
            <artifactId>hbase-client</artifactId>
            <version>2.2.2</version>
        </dependency>
        <dependency>
            <groupId>org.apache.phoenix</groupId>
            <artifactId>phoenix-core</artifactId>
            <version>5.0.0-HBase-2.0</version>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.12</version>
        </dependency>
        <dependency>
            <groupId>org.testng</groupId>
            <artifactId>testng</artifactId>
            <version>6.14.3</version>
        </dependency>
        <dependency>
            <groupId>junit</groupId>
            <artifactId>junit</artifactId>
            <version>4.13.1</version>
            <scope>test</scope>
        </dependency>
    </dependencies>
    <build>
        <plugins>
            <!-- 限制jdk版本插件 -->
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <version>3.0</version>
                <configuration>
                    <source>1.8</source>
                    <target>1.8</target>
                    <encoding>UTF-8</encoding>
                </configuration>
            </plugin>
        </plugins>
    </build>

</project>

• 代码开发

import org.junit.Before;
import org.junit.Test;

import java.sql.*;

public class PhoenixSearch {
    /**
     * 定义phoenix的url地址
     * connection
     * 构建Statement对象
     * 定义查询的sql语句,一定注意大小写
     * 构建好的对象执行sql语句
     */
    private Statement statement;
    private ResultSet rs;
    private Connection connection;

    @Before
    public void init() throws SQLException {
        //定义phoenix的url地址
        String url = "jdbc:phoenix:node02:2181";
        // connection
        connection = DriverManager.getConnection(url);
        //构建Statement对象
        statement = connection.createStatement();

    }

    @Test
    public void queryTable() throws SQLException {
        //定义查询的sql语句,一定注意大小写
        String sql="select * from USER_PHOENIX";
        //执行sql语句
        try {
            rs=statement.executeQuery(sql);
            while(rs.next()){
                System.out.println("city:"+rs.getString("city"));
                System.out.println("POPULATION :"+rs.getString("POPULATION"));
                System.out.println("STATE:"+rs.getString("STATE"));
                System.out.println("-------------------------");
            }
        } catch (SQLException e) {
            e.printStackTrace();
        } finally {
            if (connection != null) {
                connection.close();
            }
        }
    }
}

6.Phoenix构建二级索引

1、为什么需要用二级索引？

• 对于HBase而言，如果想精确地定位到某行记录，唯一的办法是通过rowkey来查询。如果不通过rowkey来查找数据，就必须逐行地比较每一列的值，即全表扫瞄。

• 对于较大的表，全表扫描的代价是不可接受的。但是，很多情况下，需要从多个角度查询数据。

  • 例如，在定位某个人的时候，可以通过姓名、身份证号、学籍号等不同的角度来查询
  • 要想把这么多角度的数据都放到rowkey中几乎不可能（业务的灵活性不允许，对rowkey长度的要求也不允许）。
  • 所以需要secondary index（二级索引）来完成这件事。secondary index的原理很简单，但是如果自己维护的话则会麻烦一些。
  • 现在，Phoenix已经提供了对HBase secondary index的支持。

  

2、Phoenix Global Indexing And Local Indexing

2.1 Global Indexing

• Global indexing，全局索引，适用于读多写少的业务场景。
• 使用Global indexing在写数据的时候开销很大，因为所有对数据表的更新操作（DELETE, UPSERT VALUES and UPSERT SELECT），都会引起索引表的更新，而索引表是分布在不同的数据节点上的，跨节点的数据传输带来了较大的性能消耗。
• 在读数据的时候Phoenix会选择索引表来降低查询消耗的时间。
  • 在默认情况下如果想查询的字段不是索引字段的话索引表不会被使用，也就是说不会带来查询速度的提升。

2.2 Local Indexing

• Local indexing，本地索引，适用于写操作频繁以及空间受限制的场景。
• 与Global indexing一样，Phoenix会自动判定在进行查询的时候是否使用索引。
• 使用Local indexing时，索引数据和数据表的数据存放在相同的服务器中，这样避免了在写操作的时候往不同服务器的索引表中写索引带来的额外开销。
• 使用Local indexing的时候即使查询的字段不是索引字段索引表也会被使用，这会带来查询速度的提升，这点跟Global indexing不同。对于Local Indexing，一个数据表的所有索引数据都存储在一个单一的独立的可共享的表中。

3、Immutable index And Mutable index

3.1 immutable index

• immutable index，不可变索引，适用于数据==只增加不更新并且按照时间先后顺序存储==（time-series data）的场景，如保存日志数据或者事件数据等。
• 不可变索引的存储方式是write one，append only。
• 当在Phoenix使用create table语句时指定IMMUTABLE_ROWS = true表示该表上创建的索引将被设置为不可变索引。
• 不可变索引分为Global immutable index和Local immutable index两种。
• Phoenix默认情况下如果在create table时不指定IMMUTABLE_ROW = true时，表示该表为mutable。

3.2 mutable index

• mutable index，可变索引，适用于数据有增删改的场景。
• Phoenix默认情况创建的索引都是可变索引，除非在create table的时候显式地指定IMMUTABLE_ROWS = true。
• 可变索引同样分为Global mutable index和Local mutable index两种。

4、配置HBase支持Phoenix二级索引

4.1 修改配置文件

• 如果要启用phoenix的二级索引功能，需要修改配置文件hbase-site.xml
• 注意：
• vim hbase-site.xml

<!-- 添加配置 -->
<property>
    <name>hbase.regionserver.wal.codec</name>
    <value>org.apache.hadoop.hbase.regionserver.wal.IndexedWALEditCodec</value>
</property>
<property>
   <name>hbase.region.server.rpc.scheduler.factory.class</name>
   <value>org.apache.hadoop.hbase.ipc.PhoenixRpcSchedulerFactory</value>
</property>
<property>
    <name>hbase.rpc.controllerfactory.class</name>
    <value>org.apache.hadoop.hbase.ipc.controller.ServerRpcControllerFactory</value>
</property>

4.2 重启hbase

• 完成上述修改后重启hbase集群使配置生效。

5、实战

5.1 在phoenix中创建表

• 首先，在phoenix中创建一个user table
• node02执行以下命令，进入phoenix客户端，并创建表

cd /kkb/install/phoenix-hbase-2.2-5.1.1-bin/
bin/sqlline.py node02:2181

create  table user (
"session_id" varchar(100) not null primary key, 
"f"."cookie_id" varchar(100), 
"f"."visit_time" varchar(100), 
"f"."user_id" varchar(100), 
"f"."age" varchar(100), 
"f"."sex" varchar(100), 
"f"."visit_url" varchar(100), 
"f"."visit_os" varchar(100), 
"f"."browser_name" varchar(100),
"f"."visit_ip" varchar(100), 
"f"."province" varchar(100),
"f"."city" varchar(100),
"f"."page_id" varchar(100), 
"f"."goods_id" varchar(100),
"f"."shop_id" varchar(100)) column_encoded_bytes=0;

5.2 导入测试数据

• 将课件当中的user50w.csv 这个文件上传到node02的/kkb/install/phoenixsql 这个路径下
  该CSV文件中有50万条记录
• node02执行以下命令，导入50W的测试数据

cd /kkb/install/phoenix-hbase-2.2-5.1.1-bin/
bin/psql.py -t USER node01:2181 /kkb/install/phoenixsql/user50w.csv

5.3 Global Indexing的二级索引测试

5.3.1 正常查询一条数据所需的时间

• 在为表USER创建secondary index之前，先看看查询一条数据所需的时间
  在node02服务器，进入phoenix的客户端，然后执行以下sql语句，查询数据，查看耗费时间

cd /kkb/install/phoenix-hbase-2.2-5.1.1-bin
bin/sqlline.py node01:2181

select * from user where "cookie_id" = '99738fd1-2084-44e9';

​ 可以看到，对名为cookie_id的列进行按值查询需要6秒左右。

​ 我们可以通过explain来查看执行计划
​ EXPLAIN(语句的执行逻辑及计划):

explain select * from user where "cookie_id" = '99738fd1-2084-44e9';

​ 由此看出先进行了全表扫描再通过过滤器来筛选出目标数据，显示这种查询方式效率是很低的。

5.3.2 给表USER创建基于Global Indexing的二级索引

• 进入到phoenix的客户端，然后执行以下命令创建索引
• 在cookie_id列上面创建二级索引：

0: jdbc:phoenix:node01:2181> create index USER_COOKIE_ID_INDEX on USER ("f"."cookie_id"); 

-- 查看当前所有表会发现多一张USER_COOKIE_ID_INDEX索引表，查询该表数据。
0: jdbc:phoenix:node01:2181> select * from USER_COOKIE_ID_INDEX limit 5;

• 再次执行查询"cookie_id"='99738fd1-2084-44e9'的数据记录

  select "cookie_id" from user where "cookie_id" = '99738fd1-2084-44e9';

  

  此时：查询速度由10秒左右减少到了毫秒级别。

  注意：select所带的字段必须包含在覆盖索引内

  EXPLAIN(语句的执行逻辑及计划):

  explain select "cookie_id" from user where "cookie_id"='99738fd1-2084-44e9';

  可以看到使用到了创建的索引USER_COOKIE_ID_INDEX。

  

5.3.3 以下查询不会用到索引表

• 虽然cookie_id是索引字段，但age不是索引字段，所以不会使用到索引

select "cookie_id","age" from user where "cookie_id"='99738fd1-2084-44e9';

• 也可以通过EXPLAIN查询语句的执行逻辑及计划

EXPLAIN select "cookie_id","age" from user where "cookie_id"='99738fd1-2084-44e9';

• 同理要查询的字段不是索引字段，也不会使用到索引表。

select "sex" from user where "cookie_id"='99738fd1-2084-44e9';

5.4 Local Indexing的二级索引测试

5.4.1 正常查询一条数据所需的时间

• 在为表USER创建secondary index之前，先看看查询一条数据所需的时间

select * from user where "user_id"='371e963d-c-487065';

• 可以看到，对名为user_id的列进行按值查询需要3秒左右。

• EXPLAIN(语句的执行逻辑及计划):

explain select * from user where "user_id"='371e963d-c-487065';

• 由此知道先进行了全表扫描再通过过滤器来筛选出目标数据，显示这种查询方式效率是很低的。

5.4.2 给表USER创建基于Local Indexing的二级索引

• 在user_id列上面创建二级索引：

create local index USER_USER_ID_INDEX on USER ("f"."user_id");

• 查看当前所有表会发现多一张USER_USER_ID_INDEX索引表，查询该表数据。

• 再次执行查询"user_id"='371e963d-c-487065'的数据记录

select * from user where "user_id"='371e963d-c-487065';

• 可以看到，对名为user_id的列进行按值查询需要0.7秒左右。

• EXPLAIN(语句的执行逻辑及计划):

explain select * from user where "user_id"='371e963d-c-487065';

​ 查看执行计划，没有执行全表扫描，效率更高了

​ 此时：查询速度由3秒左右减少到了毫秒级别。

那如果查询的字段不包含在索引表中，又如何呢？

select "user_id","age","sex" from user where "user_id"='371e963d-c-487065';

EXPLAIN(语句的执行逻辑及计划):

explain select "user_id","age","sex" from user where "user_id"='371e963d-c-487065';

​ 可以看到使用到了创建的索引USER_USER_ID_INDEX.

5.5 如何确保query查询使用Index

• 要想让一个查询使用index，有三种方式实现。

5.5.1 创建 covered index

• 如果在某次查询中，查询项或者查询条件中包含除被索引列之外的列（主键MY_PK除外）。
• 默认情况下，该查询会触发full table scan（全表扫描），但是使用covered index则可以避免全表扫描。创建包含某个字段的覆盖索引,创建方式如下：

create index USER_COOKIE_ID_AGE_INDEX on USER ("f"."cookie_id") include("f"."age");

• 查看当前所有表会发现多一张USER_COOKIE_ID_AGE_INDEX索引表，查询该表数据。

select * from USER_COOKIE_ID_AGE_INDEX limit 5;

• 查询数据

select "age" from user where "cookie_id"='99738fd1-2084-44e9';
select "age","sex" from user where "cookie_id"='99738fd1-2084-44e9';

5.5.2 在查询中提示其使用index

• 在select和column_name之间加上/*+ Index(<表名> <index表名>)*/，通过这种方式强制使用索引。

select /*+ index(user,USER_COOKIE_ID_AGE_INDEX) */ "age" from user where "cookie_id"='99738fd1-2084-44e9';

如果age是索引字段，那么就会直接从索引表中查询
如果age不是索引字段，那么将会进行全表扫描，所以当用户明确知道表中数据较少且符合检索条件时才适用，此时的性能才是最佳的。

5.5.3 使用本地索引 (创建Local Indexing 索引)

• 详细见上面

5.6 索引重建

• Phoenix的索引重建是把索引表清空后重新装配数据。

alter index USER_COOKIE_ID_INDEX on user rebuild;

5.7 删除索引

• 删除某个表的某张索引：
  语法 drop index 索引名称 on 表名
  例如：

drop  index USER_COOKIE_ID_INDEX on user;

​ 如果表中的一个索引列被删除，则索引也将被自动删除

​ 如果删除的是覆盖索引上的列，则此列将从覆盖索引中被自动删除。

6、索引性能调优

• 一般来说，索引已经很快了，不需要特别的优化。
• 这里也提供了一些方法，让你在面对特定的环境和负载的时候可以进行一些调优。下面的这些需要在hbase-site.xml文件中设置，针对所有的服务器。

1. index.builder.threads.max 
创建索引时，使用的最大线程数。 
默认值: 10。

2. index.builder.threads.keepalivetime 
创建索引的创建线程池中线程的存活时间，单位：秒。 
默认值: 60

3. index.writer.threads.max 
写索引表数据的写线程池的最大线程数。 
更新索引表可以用的最大线程数，也就是同时可以更新多少张索引表，数量最好和索引表的数量一致。 
默认值: 10

4. index.writer.threads.keepalivetime 
索引写线程池中，线程的存活时间，单位：秒。
默认值：60

5. hbase.htable.threads.max 
每一张索引表可用于写的线程数。 
默认值: 2,147,483,647

6. hbase.htable.threads.keepalivetime 
索引表线程池中线程的存活时间，单位：秒。 
默认值: 60

7. index.tablefactory.cache.size 
允许缓存的索引表的数量。 
增加此值，可以在写索引表时不用每次都去重复的创建htable，这个值越大，内存消耗越多。 
默认值: 10

8. org.apache.phoenix.regionserver.index.handler.count 
处理全局索引写请求时，可以使用的线程数。 
默认值: 30

Views: 35

前言

在数据存储的领域，有两大阵营，以B+tree为基础的关系型数据库，MySQL，SQLServer。以及以LSM-tree为基础的NoSQL key-value 存储, LevelDB。 LSM是(Log Structured Merge的简称)在分布式存储系统中通常会被设计成append-only的系统，LSM系统主要是顺序写优化，例如commit log等等，并作为分布式系统底层的基石。因此，要了解LSM的实现是十分重要的，下面主要介绍基于跳表的LSM-tree的实现 (Skiplist-Based LSM tree)。

为什么使用LSM-tree

讲LSM树之前，需要提下三种基本的存储引擎，这样才能清楚LSM树的由来：

1. 哈希存储引擎 是哈希表的持久化实现，支持增、删、改以及随机读取操作，但不支持顺序扫描，对应的存储系统为key-value存储系统。对于key-value的插入以及查询，哈希表的复杂度都是O(1)，明显比树的操作O(n)快,如果不需要有序的遍历数据，哈希表就是your Mr.Right

2. B树存储引擎是B树（关于B树的由来，数据结构以及应用场景可以看之前一篇博文）的持久化实现，不仅支持单条记录的增、删、读、改操作，还支持顺序扫描（B+树的叶子节点之间的指针），对应的存储系统就是关系数据库（Mysql等）。

3. LSM树（Log-Structured Merge Tree）存储引擎和B树存储引擎一样，同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊，LSM树和B+树相比，LSM树牺牲了部分读性能，用来大幅提高写性能。

通过以上的分析，应该知道LSM树的由来了，LSM树的设计思想非常朴素：将对数据的修改增量保持在内存中，达到指定的大小限制后将这些修改操作批量写入磁盘。所以写入性能大大提升。

不过读取的时候需要合并磁盘中历史数据和内存中最近修改操作，读取时可能需要先看是否命中内存，否则需要访问较多的磁盘文件。

极端的说，基于LSM树实现的HBase的写性能比Mysql高了一个数量级，读性能低了一个数量级。

LSM树原理把一棵大树拆分成N棵小树，它首先写入内存中，随着小树越来越大，内存中的小树会flush到磁盘中，磁盘中的树定期可以做merge操作，合并成一棵大树，以优化读性能。

以上这些大概就是HBase存储的设计主要思想，这里分别对应说明下：

1. 因为小树先写到内存中，为了防止内存数据丢失，写内存的同时需要暂时持久化到磁盘，对应了HBase的MemStore和HLog

2. MemStore上的树达到一定大小之后，需要flush到HRegion磁盘中（一般是Hadoop DataNode），这样MemStore就变成DataNode上的磁盘文件StoreFile，定期HRegionServer对DataNode的数据做merge操作，彻底删除无效空间，多棵小树在这个时机合并成大树，来增强读性能。

LSM-Tree 原理

基于跳表的LSM-tree的实现 (Skiplist-Based LSM tree，以下简称为sLSM)

sLSM有两个宏观上(macrosocopic)的组件构成，内存中的buffer和磁盘的存储(in-memory buffer and disk-based store)。内存中的数据结构主要用于快速插入和对于buffered的数据进行查询。磁盘中的数据结构主要以层级的方式来存储数据，并提供merge的操作。

sLSM的实现，是基于Skiplist。即Memtable中使用Skiplist来快速查找。这里也可以有其他方式的实现，例如AVL, B-tree等。

LSM-tree在Level的实现如下图，可以看到主要有内存和磁盘的两大数据结构组件构成。内存中的数据结构支持缓存数据的查询（近期数据的查询），磁盘中的存储是层级形式的，且是不可变的(immuatble)。

关于LSM Tree，对于最简单的二层LSM Tree而言，内存中的数据和磁盘你中的数据merge操作，如下图

图来自lsm论文

lsm tree，理论上，可以是内存中树的一部分和磁盘中第一层树做merge，对于磁盘中的树直接做update操作有可能会破坏物理block的连续性，但是实际应用中，一般lsm有多层，当磁盘中的小树合并成一个大树的时候，可以重新排好顺序，使得block连续，优化读性能。

在hbase实现中，内存部分采用跳跃表来维护一个有序的KeyValue集合memstore，数据首先写入到memstore中，为了避免memstore内存数据丢失这里引入了WAL机制，会先将数据写入到所属regionServer的WAL日志中，也即HLog。memstore的数据达到某个级别的阈值之后，会进行写盘操作，形成一个有序的数据文件是（文件内部KeyValue有序），存储在磁盘上，磁盘部分则是对应的HFile。HFile就是一个小的树，因为hbase一般是部署在hdfs上，hdfs不支持对文件的update操作，而且最终随着磁盘文件越来越多，对读的影响很大。所以内存flush到磁盘上的小树，定期也会合并成一个大树。来增强读操作的性能，整体上hbase就是用了lsm tree的思路，如下图所示。

附加资料 - 跳表数据结构

SkipList(跳表) - 这种数据结构是由William Pugh于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees，在其中详细描述了他的工作。由论文标题可知，SkipList的设计初衷是作为替换平衡树的一种选择。

什么是跳表

跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。

快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集（见右边的示意图）。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。

一张跳跃列表的示意图。每个带有箭头的框表示一个指针, 而每行是一个稀疏子序列的链表；底部的编号框（黄色）表示有序的数据序列。查找从顶部最稀疏的子序列向下进行, 直至需要查找的元素在该层两个相邻的元素中间。

跳表的演化过程

对于单链表来说，即使数据是已经排好序的，想要查询其中的一个数据，只能从头开始遍历链表，这样效率很低，时间复杂度很高，是 O(n)。

那我们有没有什么办法来提高查询的效率呢？我们可以为链表建立一个“索引”，这样查找起来就会更快，如下图所示，我们在原始链表的基础上，每两个结点提取一个结点建立索引，我们把抽取出来的结点叫做索引层或者索引，down 表示指向原始链表结点的指针。

现在如果我们想查找一个数据，比如说 15，我们首先在索引层遍历，当我们遍历到索引层中值为 14 的结点时，我们发现下一个结点的值为 17，所以我们要找的 15 肯定在这两个结点之间。这时我们就通过 14 结点的 down 指针，回到原始链表，然后继续遍历，这个时候我们只需要再遍历两个结点，就能找到我们想要的数据。好我们从头看一下，整个过程我们一共遍历了 7 个结点就找到我们想要的值，如果没有建立索引层，而是用原始链表的话，我们需要遍历 10 个结点。

通过这个例子我们可以看出来，通过建立一个索引层，我们查找一个基点需要遍历的次数变少了，也就是查询的效率提高了。

那么如果我们给索引层再加一层索引呢？遍历的结点会不会更少呢，效率会不会更高呢？我们试试就知道了。

现在我们再来查找 15，我们从第二级索引开始，最后找到 15，一共遍历了 6 个结点，果然效率更高。

当然，因为我们举的这个例子数据量很小，所以效率提升的不是特别明显，如果数据量非常大的时候，我们多建立几层索引，效率提升的将会非常的明显，感兴趣的可以自己试一下，这里我们就不举例子了。

这种通过对链表加多级索引的机构，就是跳表了。

跳表具体有多快

通过上边的例子我们知道，跳表的查询效率比链表高，那具体高多少呢？下面我们一起来看一下。

衡量一个算法的效率我们可以用时间复杂度，这里我们也用时间复杂度来比较一下链表和跳表。前面我们已经讲过了，链表的查询的时间复杂度为 O(n)，那跳表的呢？

如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)。

假如一共有 m 级索引，第 m 级的结点数为两个，通过上边我们找到的规律，那么得出 n/(2^m)=2，从而求得 m=log(n)-1。如果加上原始链表，那么整个跳表的高度就是 log(n)。我们在查询跳表的时候，如果每一层都需要遍历 k 个结点，那么最终的时间复杂度就为 O(k*log(n))。

那这个 k 值为多少呢，按照我们每两个结点提取一个基点建立索引的情况，我们每一级最多需要遍历两个个结点，所以 k=2。为什么每一层最多遍历两个结点呢？

因为我们是每两个结点提取一个结点建立索引，最高一级索引只有两个结点，然后下一层索引比上一层索引两个结点之间增加了一个结点，也就是上一层索引两结点的中值，看到这里是不是想起来我们前边讲过的二分查找，每次我们只需要判断要找的值在不在当前结点和下一个结点之间即可。

如上图所示，我们要查询红色结点，我们查询的路线即黄线表示出的路径查询，每一级最多遍历两个结点即可。

所以跳表的查询任意数据的时间复杂度为 O(2*log(n))，前边的常数 2 可以忽略，为 O(log(n))。

跳表是用空间来换时间

跳表的效率比链表高了，但是跳表需要额外存储多级索引，所以需要的更多的内存空间。

跳表的空间复杂度分析并不难，如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)，我们可以看出来这是一个等比数列。

这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2，所以跳表的空间复杂度为 o(n)。

那么我们有没有办法减少索引所占的内存空间呢？可以的，我们可以每三个结点抽取一个索引，或者没五个结点抽取一个索引。这样索引结点的数量减少了，所占的空间也就少了。

跳表的插入和删除

我们想要为跳表插入或者删除数据，我们首先需要找到插入或者删除的位置，然后执行插入或删除操作，前边我们已经知道了，跳表的查询的时间复杂度为 O(logn），因为找到位置之后插入和删除的时间复杂度很低，为 O(1)，所以最终插入和删除的时间复杂度也为 O(longn)。

我么通过图看一下插入的过程。

删除操作的话，如果这个结点在索引中也有出现，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点。当然，如果我们用的是双向链表，就不需要考虑这个问题了。

如果我们不停的向跳表中插入元素，就可能会造成两个索引点之间的结点过多的情况。结点过多的话，我们建立索引的优势也就没有了。所以我们需要维护索引与原始链表的大小平衡，也就是结点增多了，索引也相应增加，避免出现两个索引之间结点过多的情况，查找效率降低。

跳表是通过一个随机函数来维护这个平衡的，当我们向跳表中插入数据的的时候，我们可以选择同时把这个数据插入到索引里，那我们插入到哪一级的索引呢，这就需要随机函数，来决定我们插入到哪一级的索引中。

这样可以很有效的防止跳表退化，而造成效率变低。

跳表的代码实现

最后我们来看一下跳变用代码怎么实现。

package skiplist;

import java.util.Random;

/**
 * 跳表的一种实现方法。
 * 跳表中存储的是正整数，并且存储的是不重复的。
 */
public class SkipList {

  private static final int MAX_LEVEL = 16;

  private static final float SKIPLIST_P = 0.5f;

  private int levelCount = 1;

  private Node head = new Node();  // 带头链表

  private Random r = new Random();

  public Node find(int value) {
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }

  public void insert(int value) {
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    for (int i = 0; i < level; ++i) {
      update[i] = head;
    }

    // record every level largest value which smaller than insert value in update[]
    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;// use update save node in search path
    }

    // in search path node next node become new node forwords(next)
    for (int i = 0; i < level; ++i) {
      newNode.forwards[i] = update[i].forwards[i];
      update[i].forwards[i] = newNode;
    }

    // update node hight
    if (levelCount < level) levelCount = level;
  }

  public void delete(int value) {
    Node[] update = new Node[levelCount];
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
          update[i].forwards[i] = update[i].forwards[i].forwards[i];
        }
      }
    }
  }

 // 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
  // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
  // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
  //        50%的概率返回 1
  //        25%的概率返回 2
  //      12.5%的概率返回 3 ...
  private int randomLevel() {
    int level = 1;

    while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
      level += 1;
    return level;
  }

  public void printAll() {
    Node p = head;
    while (p.forwards[0] != null) {
      System.out.print(p.forwards[0] + " ");
      p = p.forwards[0];
    }
    System.out.println();
  }

  public class Node {
    private int data = -1;
    private Node forwards[] = new Node[MAX_LEVEL];
    private int maxLevel = 0;

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("{ data: ");
      builder.append(data);
      builder.append("; levels: ");
      builder.append(maxLevel);
      builder.append(" }");

      return builder.toString();
    }
  }

}

Views: 26