Indri中的动态文档索引技术

戴维 译

 

摘要： Indri 动态文档索引的实现技术，支持在更新索引的同时处理用户在线查询请求。 文本搜索引擎曾被设计为针对固定的文档集合进行查询，对不少应用来说，这种机制工作得很好，然而对于诸于新闻，财经和桌面搜索而言，需要的是高效、经常性的更新索引。 以往支持动态文档集合的研究主要围绕增量索引方法，增量系统通过往已有的索引中追加大的文档集合来优化索引性能，但是不允许在增量索引的同时处理用户查询。 与以往的增量系统不同，Indri搜索引擎的最新版本支持动态文档集合，不需要通过加大文档集合大小来获取索引性能，同时Indri支持索引和查询的并发，允许用户在增量索引的同时进行查询。

 

1．介绍

尽管全文索引技术已经出现了几十年之久，但是直到互联网的出现，它才真正得到普及。现在，几乎每个互联网使用者都是搜索引擎用户，全文搜索技术被广泛地用于各种应用领域，如Web搜索，新闻搜索，以及时下流行的桌面搜索等。

       搜索桌面（或硬盘）文件和e-mails对大多数信息检索系统而言是一个新的挑战。用户期望他们的e-mails即到即索引，文件在保存到磁盘的顷刻便被索引好。永远不要期望桌面搜索用户能忍受由于索引更新所带来的存储消耗。不管是祈祷还是咒骂，用户看到了全文搜索的好处，更为普遍的事实是人们越来越发现自己离不开搜索。

       然后，更新一个全文索引是一个耗时的过程，现在的搜索引擎通过建立大量文档的倒排索引表来创建索引，一个倒排索引项包含一篇文章的无重复词语列表，以及这些词语的附加信息（如词语在文档中的位置，词性等）。一篇短小的包含100个左右不重复词语的文章，索引的时候需要更新100个倒排索引项。如果这些倒排索引是存储在磁盘上的话，更新操作将需要100次的磁盘寻址，在现有的硬件配置下，这需要一秒或更长的时间。当然，长文章耗时也越长。另外，一个随之而来的问题是，在更新索引的时候，搜索引擎是该让用户等待更新完成还是继续处理用户的查询请求呢？

       Indri搜索引擎新的版本突破了上述限制。作为Lemur[1]项目研发的一部分，Indri支持结构化查询语言，采用语言建模方法[2]，同时为了满足问答系统的需要，Indri还支持对结构化文档不同域进行查询。Indri第一个版本没有加入对增量索引的支持，但在最新的版本中允许对单个文档进行真正的实时索引。

       一个信息检索系统要处理动态的文档集合，需要解决三个关键问题。首先，要能快速地添加和删除集合中的文档，这里的快速取决于一个桌面搜索用户愿意花多长的时间来等待索引的完成，也就是说对于单个文档而言响应应该是瞬时的。其次，系统要允许查询在任何时候都能得到响应，即使是在新文档添加进文档集合的同时。另外，系统要实用，在索引和检索性能上比不支持动态文档集合的检索系统更具有竞争性。

在Indri最新版本中，我们通过引入如下设计原则来实现上述目标：

内存结构—为了避免读写磁盘，尽可能长地把数据调入内存。

加锁机制—系统在尽可能小的时间段内对数据进行加锁互斥。

只读结构—为了减少对互斥锁的依赖，系统引入只读数据结构。

后台I/O—系统采用后台线程来和低速设备进行交互，以提高索引操作性能。

多版本结构—如果一个耗时长的操作需要获取可能已经更新的数据，系统将维持此数据的多个版本来减少互斥锁的使用。

上述原则的具体运用将在文章后续部分进行详细介绍。

 

2．相关工作

       数据库研究团体已经花了几十年时间来研究数据获取并发技术。Ramakrishnan和Gehrke提出了一个通用的数据库原则[3]，Gray和Reuter则进一步深入探讨了事务处理系统[4]。

       尽管访问文档数据和访问数据库数据所遇到的问题类似，但它们之间仍然存在着显著的差别。在数据库系统中，用户特别关心的是数据的原子性，有一个经典得例子，一位银行顾客把d美元钱从一个储蓄户头转到一个支票账号，如果d美元先从储蓄户头减掉，那么这位顾客的总钱数就少了d美元；如果先往支票账号加入d美元，那么他的钱就凭空多了d美元。不管怎么样，在第一个账号改变的同时就会出现金额不一致的情况。于是，数据库中事件并发研究的一个主要任务就是确保数据库的一致性，即使是在系统操作失败的情况下也要如此。

       在我们系统中可以确保文档的插入和删除是原子操作，没有用户会看到一个文档是部分被删除或者插入的。但我们不允许多个文档的插入和删除是原子的。既然文档之间很少像数据库中记录那样相互依赖，这就不会成为我们系统的主要限制。

       虽然有上述的差异，我们仍然可以从数据库中得到借鉴。异步I/O和互斥技术被现代数据库系统广泛使用，我们也在索引系统中采用类似的多版本并发技术[5]。

       信息检索研究团体没有忽略动态文档集合，他们把研究重点放在了增量系统上，这种系统通过一次性添加大批量文档到已有索引上来代替单个文档的高效添加。这种研究并没有考虑当更新索引时系统能否继续处理查询的问题。

       Brown，Callan和Croft[6]研究了一种高效增量索引的方法。他们区别对待小于8k和大于8k的索引，当一个小的索引需要增大时，它将被拷贝到一个大的连续的倒排索引文件中。然而对于一个大的索引项则不需要移动，只需添加一个前向指针到新的存储段(segment)里面。这也使得倒排索引可以通过倒排索引文件串连起来。他们发现，当在7个簇中创建一个索引的时候，查询性能降低了6%。使用小的簇时代价偏高，在他们的模型中索引每簇大小为64M的文本所花的时间是索引每簇大小为1M的文本的8倍。

       在最近的研究中，Lester，Zobel以及Williams[7]比较了三种索引策略：占位(in-place)，合并（re-merge）以及重构（rebuild）。除了没有对连接链表进行优化外，in-place策略类似Brown所采用的方法。所有的倒排索引连续存放，如果没有足够的空间写入新数据的时候，已有数据必须被拷贝到别的地方。在re-merge策略中，新的文档簇被创建到单独的索引中，然后和已经存在的索引进行合并。rebuild策略则对已经构建的索引弃之不顾，在原始文档的基础上重新构建索引。他们研究发现，re-merge策略是最高效的更新索引的方法。但是，他们没有像Brow，Callan和Croft所作的那样，对预分配(pre-allocation)策略之间和处理大索引策略之间的差异进行比较。
       Lester，Zobel和Williams提到，在使用最小的文档簇(10个文档)的情况下，表现最好的索引策略(in-place策略)在大约7秒的时间内更新了1G的索引。相对于别的策略而言，这已经是非常快了，但是，对于单个文档的索引更新来说，这并不是个理想的策略。

       本文描述的方法类似Lucene搜索引擎，正常情况下，就像传统的批量索引一样，Lucene以分段(segment)的方式把数据写入磁盘。一旦数据被写入段中，他们就可以被查询到，并且不需要进行段的合并。这和Brown，Callan和Croft的连接链表方法有点类似，只是，把数据写入簇(batch)中需要更多的开销。为了获得更好的性能，许多文档必须被写入磁盘的一个簇(batch)中。

       如果需要快速的响应，Lucene提供一个RAMDirectory类在内存中创建索引。添加一个文档到RAMDirectory很快，因为不需要进行磁盘I/O操作。一个文档一加入RAMDirectory便可以通过一个叫做IndexWriter的对象进行查询。这也解决了文档簇对于小文档集合的问题。然而，对于大小大于机器内存的文档集合，内存索引方式将不再可用，数据必须被写入磁盘，并根据用户对索引数据的定位方式来决定，哪些数据需要驻留内存，哪些数据应该写入磁盘。 

       在我们的工作中，当需要对文档进行快速存取时，Indri使用内存索引而不是批量索引。当需要同时处理查询请求的时候，Indri会立即决定什么时候该合并索引，而什么时候该把数据写入磁盘。

 

3．策略

3.1 内存结构

       Indri采用两种类型的索引：内存索引和磁盘索引。内存索引驻留内存，而磁盘索引则存储在磁盘上。两种索引都能够处理查询，但只有内存索引能添加新的文档。Indri的磁盘索引结构是固定不变的，可以删除，但不能修改。

       大多数的信息检索系统在磁盘上为所有文档创建一个单独的索引，而Indri在创建索引的同时还会生成不同用途的索引文件，这里我们使用“索引库repository”来指代一个文档集合对应的索引及其相关数据结构。

       当在文本集合上创建索引库的时候，Indri把当前文档索引到活动的内存索引中。只要一个索引库处在打开写模式，就存在一个活动的内存索引准备接收文档。对于小的文档集合，索引数据直到索引库需要关闭的时候才写入磁盘。数据写入的同时，一个新的内存索引被创建，作为新的活动索引使用。

       用上述方法构建一个索引相当于多个检索系统同时工作。文档通常一次性加入内存索引结构，只有当达到了内存限制时才被写入磁盘。在批量系统中，磁盘和内存结构不能独立工作，索引需要经过后续处理才能用于系统查询。

       因为构建许多小的索引比构建一个单独的大索引更加高效，所以在磁盘上维持许多单独的小索引要更加有利。大的索引只有在需要合并小索引的时候才会出现，为了尽可能快地向系统中添加文档，简单地生成小的索引更有优势[7]。

       然而，从一个单独的大索引中查询比在众多小索引中寻觅要快的多，主要的原因在于磁盘寻址时间，查询所需要的大量的磁盘寻址和索引数目之间具有线性的关系。因此，重查询负载的情况下，Indri将通过合并索引的方式来减少磁盘索引数目。

3.2 加锁机制

       为了满足系统快速响应的需求，Indri必须快速地处理查询和加入文档。Indri以前的版本已经是一个有效的批量系统，可以很容易地对数据结构进行加锁，但是这也容易使查询或文档插入被长时间阻塞。为了保持快速的响应，必须确保系统中互斥锁的使用是在很短的时间内。

       我们通过只允许活动内存索引可变来减少互斥锁的加锁时间。除了一些caches外，内存索引是系统加锁时需要处理的唯一结构。而内存索引的大小是受可用内存大小限制的，它的全部内容都驻留在内存中，即算对于复杂的查询，内存索引的响应也相当快。当然，加锁时间也可以通过减少内存限制来降低。

       互斥锁也需要向内存索引中添加新的文档，为了减少加锁时间，我们确保每个文档在上锁前是被解析过的，只有当单个文档被索引的时候才加锁，然后开锁以处理查询。大多数的网页和新闻文档可以在小于1/100秒的时间内索引好，查询处理需要等待的时间相应也就很短。

       当处理查询的时候有新文档到来，系统又正好处于加锁状态，此时，系统将禁止磁盘I/O操作。这样可以显著减少主线程在持有互斥锁的情形下任务调度混乱。

3.3 只读结构

       为了减少系统在处理大卷数据时互斥锁加锁的时间，我们设法让大部分数据保持不变，对于磁盘数据来说这是基本准则。如果磁盘数据不是只读的，那么线程之间就需要在进行磁盘I/O读写时进行加锁，这可能导致加锁时数据的高度不一致。

       既然磁盘数据在写入后便不允许更改，对于读取数据来说就不用加锁。加锁策略让Indri可以充分利用多处理器系统来提高性能。大部分的查询代码路径(query code path)仅仅需要只读锁就可以了，也就是说查询处理是高度并行的，尽管它看起来似乎受到磁盘子系统的并行限制。另外，由于文本解析和索引可以同时进行，索引过程也具有可并行性。

3.4 后台I/O

如果I/O操作在查询和索引时候不能执行，就需要引入异步I /O。Indri通过一直运行如下两个线程来实现异步I/O操作：

RepositoryMaintenanceThread

RepositoryLoadThread

       这两个线程和特定的Repository相关联，如果多于一个Repository被打开，每个repository均需要对应的这样一对线程相关联。

       RepositoryLoadThread执行两项任务。一是为查询和新加入的文档载入统计数据，这种数据载入和Unix进程载入有些类似，线程标明在过去的1，5以及15分钟内处理的查询和添加的文档数目，以帮助系统决定何时该把内存数据写入磁盘。

       RepositoryLoadThread的另一项任务是检查系统的内存使用情况。如果系统使用的内存超过用户限制的25％，RepositoryLoadThread将挂起所有文档索引线程直到内存占用降下来为止，这可以防止系统在大批量文档加入的时候崩溃。对于多数可能的实时程序，如新闻播报，系统的运行决不能超出内存限制。

       RepositoryMaintenanceThread把索引写入磁盘，它是唯一能把索引数据写入磁盘，并可以从磁盘删除数据的线程，在这个线程中不需要复杂的加锁机制。该线程每分钟激活5次以检查系统当前内存占用量，如果系统使用了过多的内存，它就开始把内存数据写入磁盘。

       如上所述，创建新的磁盘索引并不是总有好处，因为许多小的磁盘索引结构对于大的磁盘索引结构来说需要更多的查询时间。为此，索引库维护线程RepositoryMaintenaceThread在写磁盘之前检查查询和文档的载入情况，如果查询相对于文档载入量更大的话，维护线程将进行索引合并而不是往磁盘中写入一个新的索引。

3.5 多版本结构

       Indri Repository可能包含多个索引，Indri维护一个称之为index_state的结构，这个结构持有指向当前索引库中所有索引的指针。索引数据在两种情况下被写入磁盘：

       内存索引MemoryIndex已经达到了它的内存限制；

       存在过多的内存索引MemoryIndex，他们需要进行合并。

在上述两种情况下，Indri把数据写入磁盘，这些数据可能已经以别的形式存在于系统中，因此index_state需要进行修改以反映数据是否被删除。

       一个解决办法是对index_state结构的读写进行互斥，然而，这种方法也可能导致在重负载情况下系统性能低下。

考虑Indri是运行在一个并行系统中，并且用户正在进行复杂的查询，这些查询每个都需要10分钟的处理时间。假如用户在两个独立的线程中提交查询，系统中就总是有两份同样的查询在运行。如果这些查询以5分钟为时间片轮流执行，A线程分别在一个小时的0，10，20，30，40和50分钟时开始运行，而B线程则分别在5，15，25，35，45和55分钟时开始执行。在一个小时开始的时候，我们对index_state的写进行加锁，当在B线程处理完一个查询前，A线程不允许处理它的下一个的查询，于是一个处理器将有5分钟的空闲时间，这是我们不希望看到的。

为了避免上述情况的出现，Indri在同一时间维持多个index_state结构，所有新的任务（如新的查询，文档的加入）使用新的index_state结构，而旧的任务继续使用旧的index_state结构，当没有用户需要使用index_state的时候，它将被删除。

在上面的例子中，这意味着线程B在使用它旧的index_state结构完成它的查询处理的同时，线程A使用新的index_state结构开始处理它的下一个查询。当线程B处理完毕当前查询，旧的index_state将不在有用户使用，从而被删除掉。

 

4．删除文档

       Indri支持删除标记。删除标记是一种弱删除方式，只是简单地隐藏文档对于用户的可见性，而不是真正的删除。文档对应的索引数据并不会真正从倒排链表，有向链表或者压缩集合中删除掉，也就是说文档中词语的计数仍然保留在语料统计数据库中。

       假设我们有一个文档集合A，以及它的一个子集B，首先创建A的索引I，然后从I中删除B对应的索引。我们只是通过把文档集合A－B添加到I’来创建一个相似的索引I’。由于包含了文档集B的数据，索引I比索引I’需要占用更多的磁盘空间。进一步，因为I和I’对应的语料统计库稍有差别，当在这两个索引上进行查询时，查询结果也会有所不同。基于如上原因，当使用Indri进行搜索的时候要谨慎地使用文档删除特性。

       尽管实际应用中，删除是个很有用的特性，但单纯的删除用处不大。删除往往被用于进行文档更新（删除旧的版本，插入新的版本）。对于桌面搜索或新闻搜索而言，经常需要更新已有文档的错误（或者过时）版本，这就显得尤为重要。

       我们采用一个简单的位图来标记文档的删除，当一个文档需要删除，就为其设置对应的比特位，任何不在位图中的比特位均假设没有被设置。因此，如果没有文档被删除，位图文件将是一个空文件。这个文件会一直扩充直到最后一个比特位被设置为非0。

       查询时，每个文档均要在打分前对照位图进行检查，只有没有被标记为删除的文档才能进行查询计分。

 

5．总结

       Indri现在可以在小于1秒的短时间片内完成文档索引并立即用于查询，这使得高速、并发访问新索引的文档所付出的代价足够小，以至Indri不需要采用特殊的批量和增量模式。Indri可以每小时索引约15G的Web数据，包括压缩和存储每个原始文档。

       在这种性能下，我们已经实现了适合新闻过滤以及桌面搜索应用的检索系统，我们相信这是第一个具有如此高性能的开源系统。

Copyright@戴维 2005.8  于北京
参考文献：

[1] Trevor Strohman, Donald Metzler, Howard Turtle, and W. Bruce Croft, Indri: A language model-based serach engine for complex queries, IA 2005: Proceedings of the 2nd International Conference on Intelligence Analysis (to appear), 2005.

[2] Donald Metzler, Victor Lavrenko, and W. Bruce Croft, Formal multiple-bernoulli models for language modeling, Proceedings of ACM SIGIR 2004, 2004, pp. 540–541.

[3] Raghu Ramakrishnan and Johannes Gehrke, Database management systems, McGraw-Hill Higher Education, 2000.

[4] Jim Gray and Andreas Reuter, Transaction processing: Concepts and techniques, Morgan Kaufmann, 1993.

[5] Philip A. Bernstein and Nathan Goodman, Multiversion concurrency control˙theory and algorithms, ACM Trans. Database Syst. 8 (1983), no. 4, 465–483.

[6] Eric W. Brown, Fast evaluation of structured queries for information retrieval, SIGIR’95: Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval (New York, NY, USA), ACM Press, 1995, pp. 30–38.

[7] Nicholas Lester, Justin Zobel, and Hugh E. Williams, In-place versus re-build versus re-merge: index maintenance strategies for text retrieval systems, Proceedings of the 27th conference on Australasian computer science, Australian Computer Society, Inc., 2004, pp. 15–23.

 
来源：Trevor Strohman    Dynamic Collections in Indri
相关链接：
http://newhaven.lti.cs.cmu.edu/indri/
 
 
 
 
 

本文设置到的配置项有




名称
描述
类型
默认




num.partitions
topic的默认分区数
int
1


log.dirs
保存日志数据的目录。如果未设置，则使用log.dir中的值
string
/tmp/kafka-logs


offsets.topic.replication.factor
offset topic复制因子（ps：就是备份数，设置的越高来确保可用性）。为了确保offset topic有效的复制因子，第一次请求offset topic时，活的broker的数量必须最少最少是配置的复制因子数。 如果不是，offset topic将创建失败或获取最小的复制因子（活着的broker，复制因子的配置）
short
3


log.index.interval.bytes
添加一个条目到offset的间隔
int
4096


首先启动kafka集群,集群中有三台Broker; 设置3个分区,3个副本;
发送topic消息
启动之后kafka-client发送一个topic为消息szz-test-topic的消息
    public static void main(String[] args) {
        Properties props = new Properties();
        props.put("bootstrap.servers", "xxx1:9092,xxx2:9092,xxx3:9092");
        props.put("acks", "all");
        props.put("retries", 0);
        props.put("batch.size", 16384);
        props.put("linger.ms", 1);
        props.put("buffer.memory", 33554432);
        props.put("key.serializer", "org.apache.kafka.common.serialization.StringSerializer");
        props.put("value.serializer", "org.apache.kafka.common.serialization.StringSerializer");
        Producer<String, String> producer = new KafkaProducer<>(props);
        for(int i = 0; i < 5; i++){
            producer.send(new ProducerRecord<String, String>("szz-test-topic", Integer.toString(i), Integer.toString(i)));
        }
        producer.close();
    }

发送了之后可以去log.dirs路径下看看


这里的3个文件夹分别代表的是3个分区; 那是因为我们配置了这个topic的分区数num.partitions=3; 和备份数offsets.topic.replication.factor=3; 这3个文件夹中的3个分区有Leader有Fllower; 那么我们怎么知道谁是谁的Leader呢？
查看topic的分区和副本
bin/kafka-topics.sh  --describe --topic szz-test-topic --zookeeper localhost:2181



可以看到查询出来显示

分区Partition-0在broker.id=0中,其余的是副本Replicas 2,1

分区Partition-1在broker.id=1中,其余的是副本Replicas 0,2

…
或者也可以通过zk来 查看leader在哪个broker上
 get /brokers/topics/src-test-topic/partitions/0/state

[zk: localhost:2181(CONNECTED) 0] get /brokers/topics/szz-test-topic/partitions/0/state
{"controller_epoch":5,"leader":0,"version":1,"leader_epoch":0,"isr":[0,1,2]}
cZxid = 0x1001995bf

分区文件都有啥
进入文件夹看到如下文件:







名称
描述
类型
默认




log.segment.bytes
单个日志文件的最大大小
int
1073741824


我们试试多发送一些消息,看它会不会生成新的 segment
public static void main(String[] args) {
        Properties props = new Properties();
        props.put("bootstrap.servers", "xxx1:9092,xxx2:9092,xxx3:9092");
        props.put("acks", "all");
        props.put("retries", 0);
        props.put("batch.size", 163840);
        props.put("linger.ms", 10);
        props.put("buffer.memory", 33554432);
        props.put("key.serializer", "org.apache.kafka.common.serialization.StringSerializer");
        props.put("value.serializer", "org.apache.kafka.common.serialization.StringSerializer");

        Producer<String, String> producer = new KafkaProducer<>(props);
        for(int i = 0; i < 1200; i++){
            //将一个消息设置大一点
            byte[] log = new byte[904800];
            String slog = new String(log);
            producer.send(new ProducerRecord<String, String>("szz-test-topic",0, Integer.toString(i),  slog));
        }
        producer.close();
    }


从图中可以看到第一个segment文件00000000000000000000.log快要满log.segment.bytes的时候就开始创建了00000000000000005084.log了;

并且.log和.index、.timeindex文件是一起出现的; 并且名称是以文件第一个offset命名的

.log存储消息文件
.index存储消息的索引
.timeIndex，时间索引文件，通过时间戳做索引

消息文件
上面的几个文件我们来使用kafka自带工具bin/kafka-run-class.sh 来读取一下都是些啥

bin/kafka-run-class.sh kafka.tools.DumpLogSegments --files 00000000000000000000.log


最后一行:
baseoffset:5083  position: 1072592768  CreateTime: 1603703296169

.index 消息索引
bin/kafka-run-class.sh kafka.tools.DumpLogSegments --files 00000000000000000000.index



最后一行:
offset:5083  position:1072592768

.timeindex 时间索引文件
bin/kafka-run-class.sh kafka.tools.DumpLogSegments --files 00000000000000000000.timeindex


最后一行:
timestamp: 1603703296169 offset: 5083

Kafka如何查找指定offset的Message的
找了个博主的图 @lizhitao



比如：要查找绝对offset为7的Message：

首先是用二分查找确定它是在哪个LogSegment中，自然是在第一个Segment中。
打开这个Segment的index文件，也是用二分查找找到offset小于或者等于指定offset的索引条目中最大的那个offset。自然offset为6的那个索引是我们要找的，通过索引文件我们知道offset为6的Message在数据文件中的位置为9807。
打开数据文件，从位置为9807的那个地方开始顺序扫描直到找到offset为7的那条Message。

Kafka 中的索引文件，以稀疏索引(sparse index)的方式构造消息的索引，它并不保证每个消息在索引文件中都有对应的索引项。每当写入一定量（由 broker 端参数 log.index.interval.bytes 指定，默认值为 4096，即 4KB）的消息时，偏移量索引文件 和 时间戳索引文件 分别增加一个偏移量索引项和时间戳索引项，增大或减小 log.index.interval.bytes 的值，对应地可以缩小或增加索引项的密度。
稀疏索引通过 MappedByteBuffer 将索引文件映射到内存中，以加快索引的查询速度。
leader-epoch-checkpoint

leader-epoch-checkpoint 中保存了每一任leader开始写入消息时的offset; 会定时更新

follower被选为leader时会根据这个确定哪些消息可用



参考文档
kafka官方文档
Kafka的Log存储解析
Kafka-工作流程，文件存储机制，索引机制，如何通过offset找到对应的消息
Broker配置文件详解


日常运维、问题排查=> 滴滴开源LogiKM一站式Kafka监控与管控平台

cJSON文档解析

cJSON是一个轻量级且易于扩展的JSON解析开源库。
github地址为：https://github.com/DaveGamble/cJSON



安装与使用


源码安装：将cJSON.c与cJSON.h这两个文件复制入自己的工程项目中，通过#include "cJSON.h"就可以使用了


编译安装


#克隆cJSON库的源码
git clone https://github.com/DaveGamble/cJSON
cd cJSON
mkdir build
cd build
cmake ..
#编译源码
make
#将头文件放入/usr/local/include/cjson文件夹中，库放入/usr/local/lib，需要超级用户的权限
sudo make install



通过#include <cjson/cJSON.h>进行使用






数据结构

cJSON使用cJSON结构体来存储JSON数据

/* cJSON结构 */
typedef struct cJSON
{
    struct cJSON *next;
    struct cJSON *prev;
    struct cJSON *child;
    int type;
    char *valuestring;
    //不应该直接向valueint写数据，而是使用cJSON_SetNumberValue函数进行赋值
    int valueint;
    double valuedouble;
    char *string;
} cJSON;


一个cJSON结构体存储一个JSON的值。cJSON结构体中的type是指向JSON值的类型，同时是以bit-flag的形式存储，这意味着不能仅仅通过比较type的值来判断JSON值的类型。
可以使用cJSON_Is...函数来检查cJSON结构体存储JSON的值的类型，它会对空指针进行检查，同时返回一个布尔值来判断否是该值。
cJSON可能的值有：

cJSON_Invalid：无效值，没有存储任何的值。当成员全部清零时便是该值
cJSON_False：为假的布尔值
cJSON_True：为真的布尔值
cJSON_NULL：空值
cJOSN_Number：数值，既作为双精度浮点数存储于valuedouble,又作为整型存储于valueint。如果数值超过了整型的范围，valueint将被赋值为INT_MAX或者INT_MIN
cJSON_String：字符串，以’\0’的形式结尾，存储于valuestring
cJSON_Array：数组，通过cJSON节点链表来存储array值，每一个元素使用next和prev进行相互连接，第一个成员的prev值为NULL，最后一个成员的next值为NULL。同时使用成员child指针来指向该链表
cJSON_Object：对象，与数组有相似的存储方式，唯一不同的是对象会将键值放入成员string中
cJSON_Raw：JSON格式的字符串，以’\0’结尾，存储于valuestring。在一次又一次的打印相同的JSON场景下，它能够节省内存。cJSON不会在解析json格式的字符串时产生这种类型。值的注意的是cJSON库不会检查其值是否是合法的
cJSON_IsReference：成员child指针或者valuestring指向的节点并不属于自己，自己仅仅是一个引用。因此，cJSON_Delete和其他相关的函数只会释放这个引用本身，而不会去释放child或者valuestring
cJSON_StringIsConst：成员string指向的是一个字面量，因此，cJSON_Delete和其他相关的函数不会试图去释放string的内存





使用这些数据结构

对于每一种类型的值都有一个对应的函数cJSON_Create...来创建。这类函数会动态分配一个cJSON的结构，所以需要在使用完后用cJSON_Delete释放掉内存，以避免内存泄漏。
注意：当你已经把一个节点加入了一个数组或者对象，你就不能在用cJSON_Delete去释放这个节点的内存了，当该数组或者对象被删除时，这个节点也会被删除



创建基本类型的函数

null：cJSON_CreateNull
booleans：cJSON_CreateTrue，cJSON_CreateFalse或者cJSON_CreateBool
numbers：cJSON_CreateNumber
strings：cJSON_CreateString



数组

你可以使用cJSON_CreateArray函数来创建一个新的空数组。cJSON_CreateArrayReference函数可以创建一个数组的引用，因为它没有属于自己的内容，所以它的子元素不会被cJSON_Delete给删除


使用cJSON_AddItemToArray函数可以在数组的最后增加元素。使用cJSON_AddItemReferenceToArray函数将会增加一个元素去引用其他的节点，这就意味着cJSON_Delete不会去删除这个元素的child或者valuestring属性，因此当这些属性在其他地方使用的时候，不用担心重复释放内存的事情发生。使用cJSON_InsertItemInArray函数可以将一个新元素插入数组中的0索引的位置，旧的元素的索引依次加1


如果你想根据索引去移除数组中的一个元素并且继续去使用它，可以使用cJSON_DetachItemFromArray函数，它将会返回被分离的数组。为避免内存泄漏，确保将返回值赋值给一个指针


当你需要替换数组中的某一个元素时，cJSON_ReplaceItemInArray函数使用索引的方式来进行替换。cJSON_ReplaceItemViaPointer函数使用指向该元素的指针，同时如果失败则会返回0。这两个函数会分离出旧的元素并删除它，同时在这个位置加入新的元素


使用cJSON_GetArraySize函数得到数组的大小。使用cJSON_GetArrayItem得到一个元素的索引


因为数组是以链表的方式进行存储的，所以通过索引的方式进行遍历效率是很低的( O(n^2) )。建议使用宏cJSON_ArrayForEach来遍历数组，它具有时间复杂度为( O(n) )



对象

你可以使用cJSON_CreateObject函数来创建一个新的空对象。cJSON_CreateObjectReference函数可以创建一个对象的引用，因为它没有属于自己的内容，所以它的子元素不会被cJSON_Delete给删除


使用cJSON_AddItemToObject函数来增加一个元素到对象里。使用cJSON_AddItemToObjectCS函数来增加对象里的元素时，使用的键值（结构体cJSON中string成员）是一个引用或者是字面量，因此它会被cJSON_Delete给忽略。使用cJSON_AddItemReferenceToArray函数将会增加一个元素去引用其他的节点，这就意味着cJSON_Delete不会去删除这个元素的child或者valuestring属性，因此当这些属性在其他地方使用的时候，不用担心重复释放内存的事情发生


使用cJSON_DetachItemFromObjectCaseSensitive函数来从对象中分离出一个元素，从函数命名可以看出对于指定的键值是大小写敏感的，它将会返回被分离的数组。为避免内存泄漏，确保将返回值赋值给一个指针


使用cJSON_DeleteItemFromObjectCaseSensitive函数来从一个对象中删除一个元素，可以把它看成先从对象中分离出该元素然后在删除


当你需要替换对象中的某一个元素时，cJSON_ReplaceItemInObjectCaseSensitive函数使用j键值查找的方式来进行替换。cJSON_ReplaceItemViaPointer函数使用指向该元素的指针来查找并替换，同时如果失败则会返回0。这两个函数会分离出旧的元素并删除它，同时在这个位置加入新的元素


因为对象的存储方式和数组很像，所以同样可以通过cJSON_GetArraySize来得到对象里元素的个数


使用cJSON_GetObjectItemCaseSensitive来访问对象中的某一个元素


使用宏cJSON_ArrayForEach来遍历一个对象


cJSON同样也提供便利的工具函数来快速的在对象内部创建一个新的元素，比如说cJSON_AddNullToObject函数将会返回新加的元素指针，如果失败则返回NULL





解析JSON字符串

可以使用cJSON_Parse函数来一些以’\0’结尾的字符串进行解析

cJSON *json = cJSON_Parse(string);


解析后的结果是cJSON的树状的数据结构，一旦解析成功，就有责任在使用完后使用cJSON_Delete释放内存


默认分配内存使用的是malloc函数，释放内存使用的是free函数。但是可以使用cJSON_InitHooks函数来全局性改变


当一个错误发生时，cJSON_GetErrorPtr函数可以得到指向输入字符串中错误的位置的指针。值的注意的是在多线程的情况下，该函数会产生竞争条件，更好的方法是使用带有return_parse_end参数的cJSON_ParseWithOpts函数。


如果你想有更多的选项，使用cJSON_ParseWithOpts(const char *value, const char **return_parse_end, cJSON_bool require_null_terminated)函数，return_parse_end返回输入的JSON字符串的结尾或者一个错误发生的地方（从而在保障线程安全的情况下替换cJSON_GetErrorPtr函数）。require_null_terminated如果该值设为1，那么当输入的字符串在有效的以’\0’结尾的json字符串后还包含其他的数据，就会报错



打印JSON

使用cJSON_Print函数将一个cJSON数据结构打印为字符串

char *string = cJSON_Print(json);


该函数将会动态分配内存给一个字符串，将JSON表达式放入其中。一旦该函数返回，就有责任释放该内存（默认是free，取决于设置的cJSON_InitHooks）


cJSON_Print将会用空白符来格式化JSON字符串。可以使用cJSON_PrintUnformatted来无格式化的打印


如果你关于返回的结果的字符串的大小有一个想法，你可以使用cJSON_PrintBuffered(const cJSON *item, int prebuffer, cJSON_bool fmt)函数。fmt是一个决定是否用空白字符格式化JSON字符串，prebuffer指出了所用的第一个缓冲区大小。cJOSN_Print当前使用256字节的缓冲区大小。一旦打印超过了大小，新的缓冲区会被动态分配，在继续打印之前旧的缓冲区里的内容复制到新的缓冲区里。


使用cJSON_PrintPreallocated(cJSON *item, char *buffer, const int length, const cJSON_bool format)函数可以完全避免动态的内存分配，该函数需要指向缓冲区的指针和该缓冲区的大小，如果缓冲区过小，打印将会失败，函数返回0。一旦成功，函数返回1。值得注意的是需要准备超过实际需要的字节还要多5个字节，因为cJSON并不是100%的精确估计提供的内存是否足够



示例


在这个例子里，我们想去构建一个JSON并解析它
{
    "name": "Awesome 4K",
    "resolutions": [
        {
            "width": 1280,
            "height": 720
        },
        {
            "width": 1920,
            "height": 1080
        },
        {
            "width": 3840,
            "height": 2160
        }
    ]
}



构建以上的json，然后打印成字符串
//create a monitor with a list of supported resolutions
char* create_monitor(void)
{
    const unsigned int resolution_numbers[3][2] = {
        {1280, 720},
        {1920, 1080},
        {3840, 2160}
    };
    char *string = NULL;
    cJSON *name = NULL;
    cJSON *resolutions = NULL;
    cJSON *resolution = NULL;
    cJSON *width = NULL;
    cJSON *height = NULL;
    size_t index = 0;

    cJSON *monitor = cJSON_CreateObject();
    if (monitor == NULL)
    {
        goto end;
    }

    name = cJSON_CreateString("Awesome 4K");
    if (name == NULL)
    {
        goto end;
    }
    /* after creation was successful, immediately add it to the monitor,
     * thereby transfering ownership of the pointer to it */
    cJSON_AddItemToObject(monitor, "name", name);

    resolutions = cJSON_CreateArray();
    if (resolutions == NULL)
    {
        goto end;
    }
    cJSON_AddItemToObject(monitor, "resolutions", resolutions);

    for (index = 0; index < (sizeof(resolution_numbers) / (2 * sizeof(int))); ++index)
    {
        resolution = cJSON_CreateObject();
        if (resolution == NULL)
        {
            goto end;
        }
        cJSON_AddItemToArray(resolutions, resolution);

        width = cJSON_CreateNumber(resolution_numbers[index][0]);
        if (width == NULL)
        {
            goto end;
        }
        cJSON_AddItemToObject(resolution, "width", width);

        height = cJSON_CreateNumber(resolution_numbers[index][1]);
        if (height == NULL)
        {
            goto end;
        }
        cJSON_AddItemToObject(resolution, "height", height);
    }

    string = cJSON_Print(monitor);
    if (string == NULL)
    {
        fprintf(stderr, "Failed to print monitor.\n");
    }

end:
    cJSON_Delete(monitor);
    return string;
}



我们可以使用cJSON_Add...ToObject辅助函数来更方便构建
char *create_monitor_with_helpers(void)
{
    const unsigned int resolution_numbers[3][2] = {
        {1280, 720},
        {1920, 1080},
        {3840, 2160}
    };
    char *string = NULL;
    cJSON *resolutions = NULL;
    size_t index = 0;

    cJSON *monitor = cJSON_CreateObject();

    if (cJSON_AddStringToObject(monitor, "name", "Awesome 4K") == NULL)
    {
        goto end;
    }

    resolutions = cJSON_AddArrayToObject(monitor, "resolutions");
    if (resolutions == NULL)
    {
        goto end;
    }

    for (index = 0; index < (sizeof(resolution_numbers) / (2 * sizeof(int))); ++index)
    {
        cJSON *resolution = cJSON_CreateObject();

        if (cJSON_AddNumberToObject(resolution, "width", resolution_numbers[index][0]) == NULL)
        {
            goto end;
        }

        if(cJSON_AddNumberToObject(resolution, "height", resolution_numbers[index][1]) == NULL)
        {
            goto end;
        }

        cJSON_AddItemToArray(resolutions, resolution);
    }

    string = cJSON_Print(monitor);
    if (string == NULL) {
        fprintf(stderr, "Failed to print monitor.\n");
    }

end:
    cJSON_Delete(monitor);
    return string;
}



解析并测试
/* return 1 if the monitor supports full hd, 0 otherwise */
int supports_full_hd(const char * const monitor)
{
    const cJSON *resolution = NULL;
    const cJSON *resolutions = NULL;
    const cJSON *name = NULL;
    int status = 0;
    cJSON *monitor_json = cJSON_Parse(monitor);
    if (monitor_json == NULL)
    {
        const char *error_ptr = cJSON_GetErrorPtr();
        if (error_ptr != NULL)
        {
            fprintf(stderr, "Error before: %s\n", error_ptr);
        }
        status = 0;
        goto end;
    }

    name = cJSON_GetObjectItemCaseSensitive(monitor_json, "name");
    if (cJSON_IsString(name) && (name->valuestring != NULL))
    {
        printf("Checking monitor \"%s\"\n", name->valuestring);
    }

    resolutions = cJSON_GetObjectItemCaseSensitive(monitor_json, "resolutions");
    cJSON_ArrayForEach(resolution, resolutions)
    {
        cJSON *width = cJSON_GetObjectItemCaseSensitive(resolution, "width");
        cJSON *height = cJSON_GetObjectItemCaseSensitive(resolution, "height");

        if (!cJSON_IsNumber(width) || !cJSON_IsNumber(height))
        {
            status = 0;
            goto end;
        }

        if ((width->valuedouble == 1920) && (height->valuedouble == 1080))
        {
            status = 1;
            goto end;
        }
    }

end:
    cJSON_Delete(monitor_json);
    return status;
}


值的注意的是，对于cJSON_Parse函数的返回结果没有空指针的检查，因为cJSON_GetObjectItemCaseSensitive对于输入空指针有检查

              mysql使用索引能提高查询效率，但在有些情况下，你使用索引查询，索引并没有起作用。

mysql> select * from stu;
+------+------+----------+
| id   | age  | name     |
+------+------+----------+
|    1 |    1 | zhangsan |
|    2 |    2 | lisi     |
|    3 |    3 | wangwu   |
|    4 |    4 | zhaoliu  |
|    5 |    5 | sunqi    |
+------+------+----------+
5 rows in set (0.00 sec)

mysql> show index from stu;
+-------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name   | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| stu   |          1 | index_name |            1 | name        | A         |           5 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.00 sec)

可以看到stu表中的name字段为该表的索引。

mysql> explain select * from stu where name like 'z%';
+----+-------------+-------+------------+-------+---------------+------------+---------+------+------+----------+-----------------------+
| id | select_type | table | partitions | type  | possible_keys | key        | key_len | ref  | rows | filtered | Extra                 |
+----+-------------+-------+------------+-------+---------------+------------+---------+------+------+----------+-----------------------+
|  1 | SIMPLE      | stu   | NULL       | range | index_name    | index_name | 23      | NULL |    2 |   100.00 | Using index condition |
+----+-------------+-------+------------+-------+---------------+------------+---------+------+------+----------+-----------------------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select * from stu where name like '%i';
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | stu   | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    5 |    20.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)


由结果可以看到，like 'z%'使用了索引查询，而like '%i'没有使用索引查询。key为index_name表示使用了索引查询。

关于like的查询：如果匹配字串的第一个字符为'%'，索引不会起作用。只有'%'不在第一个位置，索引才会起作用。

mysql> create index index_id_age on stu(id,age);
Query OK, 0 rows affected (0.02 sec)
Records: 0  Duplicates: 0  Warnings: 0

mysql> show index from stu;
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table | Non_unique | Key_name     | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| stu   |          1 | index_id_age |            1 | id          | A         |           5 |     NULL | NULL   | YES  | BTREE      |         |               |
| stu   |          1 | index_id_age |            2 | age         | A         |           5 |     NULL | NULL   | YES  | BTREE      |         |               |
+-------+------------+--------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
2 rows in set (0.00 sec)

mysql> explain select * from stu where id=4;
+----+-------------+-------+------------+------+---------------+--------------+---------+-------+------+----------+-------+
| id | select_type | table | partitions | type | possible_keys | key          | key_len | ref   | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+--------------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | stu   | NULL       | ref  | index_id_age  | index_id_age | 5       | const |    1 |   100.00 | NULL  |
+----+-------------+-------+------------+------+---------------+--------------+---------+-------+------+----------+-------+
1 row in set, 1 warning (0.00 sec)

mysql> explain select * from stu where age=4;
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
|  1 | SIMPLE      | stu   | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    5 |    20.00 | Using where |
+----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
1 row in set, 1 warning (0.00 sec)


我们为表stu创建了一个多列索id和age。当我们单独使用id时，查询使用了索引；而当单独使用age时，查询没有使用索引。则对应多列索引，只有当查询使用了这些字段的第一个字段时，索引才会被使用。

 

当查询条件使用or关键字时，且or前后的两个条件中的列都是索引时，查询中才使用索引。否则将不使用索引。

我目前机器上测试的结果是：or前后都使用索引，查询还是不用索引，不知何故。感兴趣的读者可以在自己mysql上尝试一下。

 

 

参考资料：mysql从入门到精通