A simple B+ tree example linking the keys 1–7 to data values d₁-d₇. The linked list (red) allows rapid in-order traversal.

In computer science, a B+ tree or B plus tree is a type of tree which represents sorted data in a way that allows for efficient insertion, retrieval and removal of records, each of which is identified by a key. It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a "block" or "node"). In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.

The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context—in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree.

NTFS, ReiserFS, NSS, XFS, and JFS filesystems all use this type of tree for metadata indexing. Relational database management systems such as IBM DB2^[1], Informix^[1], Microsoft SQL Server^[1], Oracle 8^[1], Sybase ASE^[1], PostgreSQL^[2], Firebird, MySQL^[3] and SQLite^[4] support this type of tree for table indices. Key-value database management systems such as CouchDB^[5], Tokyo Cabinet^[6] and Tokyo Tyrant support this type of tree for data access. InfinityDB^[7] is a concurrent BTree.

[edit] Details

The order, or branching factor b of a B+ tree measures the capacity of nodes (i.e. the number of children nodes) for internal nodes in the tree. The actual number of children for a node, referred to here as m, is constrained for internal nodes so that . The root is an exception: it is allowed to have as few as two children. For example, if the order of a B+ tree is 7, each internal node (except for the root) may have between 4 and 7 children; the root may have between 2 and 7. Leaf nodes have no children , but are constrained so that the number of keys must be at least and at most b − 1. In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary.

[edit] Search

The algorithm to perform a search for a record r follows pointers to the correct child of each node until a leaf is reached. Then, the leaf is scanned until the correct record is found (or until failure).

  function search(record r)
    u := root
    while (u is not a leaf) do
      choose the correct pointer in the node
      move to the first node following the pointer
      u := current node
    scan u for r

This pseudocode assumes that no repetition is allowed.

[edit] Insertion

Perform a search to determine what bucket the new record should go in.

• if the bucket is not full, add the record.
• otherwise, split the bucket.
  • allocate new leaf and move half the bucket's elements to the new bucket
  • insert the new leaf's smallest key and address into the parent.
  • if the parent is full, split it also
    • add the middle key to the parent node
  • repeat until a parent is found that need not split
• if the root splits, create a new root which has one key and two pointers.

[edit] Characteristics

For a b-order B+ tree with h levels of index:

• The maximum number of records stored is n_max = b^h − b^{h − 1}
• The minimum number of keys is
• The space required to store the tree is O(n)
• Inserting a record requires O(log_bn) operations in the worst case
• Finding a record requires O(log_bn) operations in the worst case
• Removing a (previously located) record requires O(log_bn) operations in the worst case
• Performing a range query with k elements occurring within the range requires O(log_bn + k) operations in the worst case.

[edit] Implementation

The leaves (the bottom-most index blocks) of the B+ tree are often linked to one another in a linked list; this makes range queries or an (ordered) iteration through the blocks simpler and more efficient (though the aforementioned upper bound can be achieved even without this addition). This does not substantially increase space consumption or maintenance on the tree. This illustrates one of the significant advantages of a B+-tree over a B-tree; in a B-tree, since not all keys are present in the leaves, such an ordered linked list cannot be constructed. A B+-tree is thus particularly useful as a database system index, where the data typically resides on disk, as it allows the B+-tree to actually provide an efficient structure for housing the data itself (this is described in ^[8] as index structure "Alternative 1").

If a storage system has a block size of B bytes, and the keys to be stored have a size of k, arguably the most efficient B+ tree is one where b = (B / k) − 1. Although theoretically the one-off is unnecessary, in practice there is often a little extra space taken up by the index blocks (for example, the linked list references in the leaf blocks). Having an index block which is slightly larger than the storage system's actual block represents a significant performance decrease; therefore erring on the side of caution is preferable.

If nodes of the B+ tree are organized as arrays of elements, then it may take a considerable time to insert or delete an element as half of the array will need to be shifted on average. To overcome this problem, elements inside a node can be organized in a binary tree or a B+ tree instead of an array.

B+ trees can also be used for data stored in RAM. In this case a reasonable choice for block size would be the size of processor's cache line. However, some studies have proved that a block size a few times larger than the processor's cache line can deliver better performance if cache prefetching is used.

Space efficiency of B+ trees can be improved by using some compression techniques. One possibility is to use delta encoding to compress keys stored into each block. For internal blocks, space saving can be achieved by either compressing keys or pointers. For string keys, space can be saved by using the following technique: Normally the ith entry of an internal block contains the first key of block i+1. Instead of storing the full key, we could store the shortest prefix of the first key of block i+1 that is strictly greater (in lexicographic order) than last key of block i. There is also a simple way to compress pointers: if we suppose that some consecutive blocks i, i+1...i+k are stored contiguously, then it will suffice to store only a pointer to the first block and the count of consecutive blocks.

All the above compression techniques have some drawbacks. First, a full block must be decompressed to extract a single element. One technique to overcome this problem is to divide each block into sub-blocks and compress them separately. In this case searching or inserting an element will only need to decompress or compress a sub-block instead of a full block. Another drawback of compression techniques is that the number of stored elements may vary considerably from a block to another depending on how well the elements are compressed inside each block.

[edit] History

The B tree was first described in the paper Organization and Maintenance of Large Ordered Indices. Acta Informatica 1: 173–189 (1972) by Rudolf Bayer and Edward M. McCreight. There is no single paper introducing the B+ tree concept. Instead, the notion of maintaining all data in leaf nodes is repeatedly brought up as an interesting variant. An early survey of B trees also covering B+ trees is Douglas Comer: "The Ubiquitous B-Tree", ACM Computing Surveys 11(2): 121–137 (1979). Comer notes that the B+ tree was used in IBM's VSAM data access software and he refers to an IBM published article from 1973.

[edit] See also

• Binary Search Tree
• B# Tree
• B-tree
• Bitmap index
• Divide and conquer algorithm

[edit] References

[edit] External links

Wikibooks has a book on the topic of Transwiki:B+ tree

• B+ tree in Python, used to implement a list
• B+ tree implementation as C++ template library
• Dr. Monge's B+ Tree index notes
• Open Source C++ B+ Tree Implementation
• Interactive B+ Tree Implementation in C
• Open Source Javascript B+ Tree Implementation
• Perl implementation of B+ trees
• java/C#/python implementations of B+ trees
• Evaluating the performance of CSB+-trees on Mutithreaded Architectures
• Effect of node size on the performance of cache conscious B+-trees
• Fractal Prefetching B+-trees
• Towards pB+-trees in the field: implementations Choices and performance
• Cache-Conscious Index Structures for Main-Memory Databases
• Cache Oblivious B(+)-trees
• The Power of B-Trees: CouchDB B+ Tree Implementation

Simple example of an R-tree for 2D rectangles

Visualization of an R*-tree for 3D cubes using ELKI

R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods, i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 kilometres (1.2 mi) of my current location".

The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (MBRs, otherwise known as bounding boxes, i.e. "rectangle", what the "R" in R-tree stands for).

Each node of an R-tree has a variable number of entries (up to some pre-defined maximum). Each entry within a non-leaf node stores two pieces of data: a way of identifying a child node, and the bounding box of all entries within this child node.

The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that "nearby" elements are placed in the same leaf node (in particular, a new element will go into the leaf node that requires the least enlargement in its bounding box). Each entry within a leaf node stores two pieces of information; a way of identifying the actual data element (which, alternatively, may be placed directly in the node), and the bounding box of the data element.

Similarly, the searching algorithms (e.g., intersection, containment, nearest) use the bounding boxes to decide whether or not to search inside a child node. In this way, most of the nodes in the tree are never "touched" during a search. Like B-trees, this makes R-trees suitable for databases, where nodes can be paged to memory when needed.

Different algorithms can be used to split nodes when they become too full, resulting in the quadratic and linear R-tree sub-types.

R-trees do not historically guarantee good worst-case performance, but generally perform well with real-world data.^{[citation needed]} However, a new algorithm was published in 2004 that defines the Priority R-Tree, which claims to be as efficient as the most efficient methods of 2004 and is at the same time worst-case optimal.^[1]

When data is organized in an R-Tree, the k nearest neighbors (for any L^p-Norm) of all points can efficiently be computed using a spatial join^[2]. This is beneficial for many algorithms based on the k nearest neighbors, for example the Local Outlier Factor.

[edit] Variants

• R* tree
• R+ tree
• Hilbert R-tree
• Priority R-Tree (PR-Tree) - The PR-tree performs similarly to the best known R-tree variants on real-life and relatively evenly distributed data, but outperforms them significantly on more extreme data.^[1]

[edit] Algorithm

[edit] Search

The input is a search rectangle (Query box). Searching is quite similar to searching in a B+tree. The search starts from the root node of the tree. Every internal node contains a set of rectangles and pointers to the corresponding child node and every leaf node contains the rectangles of spatial objects (the pointer to some spatial object can be there). For every rectangle in a node, it has to be decided if it overlaps the search rectangle or not. If yes, the corresponding child node has to be searched also. Searching is done like this in a recursive manner until all overlapping nodes have been traversed. When a leaf node is reached, the contained bounding boxes (rectangles) are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.

[edit] Insertion

To insert an object, the tree is traversed recursively from the root node. All rectangles in the current internal node are examined. The constraint of least coverage is employed to insert an object, i.e., the box that needs least enlargement to enclose the new object is selected. In the case where there is more than one rectangle that meets this criterion, the one with the smallest area is chosen. Inserting continues recursively in the chosen node. Once a leaf node is reached, a straightforward insertion is made if the leaf node is not full. If the leaf node is full, it must be split before the insertion is made. A few splitting algorithms have been proposed for good R-tree performance.

This section requires expansion.

[edit] Bulk-loading

• Sort-Tile-Recursive (STR) ^[3]
• Packed Hilbert R-Tree - Uses the Hilbert value of the center of a rectangle to sort the leaf nodes and recursively builds the tree.
• Nearest-X - Rectangles are sorted on the x-coordinate and nodes are created.

This section requires expansion.

[edit] See also

• Segment tree
• Interval tree - A degenerate R-Tree for 1 dimension (usually time).
• Bounding volume hierarchy
• Spatial index
• GiST

[edit] References

1. ^ ^{a b} Lars Arge, Mark de Berg, Herman J. Haverkort, Ke Yi: ""The Priority R-Tree: A Practically Efficient and Worst-Case Optimal RTree"", SIGMOD 2004, June 13–18, Paris, France
2. ^ Brinkhoff, T.; Kriegel, H. P.; Seeger, B. (1993). "Efficient processing of spatial joins using R-trees". ACM SIGMOD Record 22: 237. doi:10.1145/170036.170075.  edit
3. ^ Scott T. Leutenegger, Jeffrey M. Edgington and Mario A. Lopez: STR: A Simple and Efficient Algorithm for R-Tree Packing

• Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47–57. ISBN 0-89791-128-8
• Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees: Theory and Applications, Springer, 2005. ISBN 1-85233-977-2
• N. Beckmann, H.-P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331

[edit] External links

• R-tree portal
• R-Tree implementations: C & C++, Java applet, Common Lisp, Python, Javascript.

Author LiuDong

首先我们先介绍一下为什么要让 Apache 与 Tomcat 之间进行连接。事实上 Tomcat 本身已经提供了 HTTP 服务，该服务默认的端口是 8080，装好 tomcat 后通过 8080 端口可以直接使用 Tomcat 所运行的应用程序，你也可以将该端口改为 80。

既然 Tomcat 本身已经可以提供这样的服务，我们为什么还要引入 Apache 或者其他的一些专门的 HTTP 服务器呢？原因有下面几个：

1. 提升对静态文件的处理性能

2. 利用 Web 服务器来做负载均衡以及容错

3. 无缝的升级应用程序

这三点对一个 web 网站来说是非常之重要的，我们希望我们的网站不仅是速度快，而且要稳定，不能因为某个 Tomcat 宕机或者是升级程序导致用户访问不了，而能完成这几个功能的、最好的 HTTP 服务器也就只有 apache 的 http server 了，它跟 tomcat 的结合是最紧密和可靠的。

接下来我们介绍三种方法将 apache 和 tomcat 整合在一起。

JK

这是最常见的方式，你可以在网上找到很多关于配置JK的网页，当然最全的还是其官方所提供的文档。JK 本身有两个版本分别是 1 和 2，目前 1 最新的版本是 1.2.19，而版本 2 早已经废弃了，以后不再有新版本的推出了，所以建议你采用版本 1。

JK 是通过 AJP 协议与 Tomcat 服务器进行通讯的，Tomcat 默认的 AJP Connector 的端口是 8009。JK 本身提供了一个监控以及管理的页面 jkstatus，通过 jkstatus 可以监控 JK 目前的工作状态以及对到 tomcat 的连接进行设置，如下图所示：

在这个图中我们可以看到当前JK配了两个连接分别到 8109 和 8209 端口上，目前 s2 这个连接是停止状态，而 s1 这个连接自上次重启后已经处理了 47 万多个请求，流量达到 6.2 个 G，最大的并发数有 13 等等。我们也可以利用 jkstatus 的管理功能来切换 JK 到不同的 Tomcat 上，例如将 s2 启用，并停用 s1，这个在更新应用程序的时候非常有用，而且整个切换过程对用户来说是透明的，也就达到了无缝升级的目的。关于 JK 的配置文章网上已经非常多了，这里我们不再详细的介绍整个配置过程，但我要讲一下配置的思路，只要明白了配置的思路，JK 就是一个非常灵活的组件。

JK 的配置最关键的有三个文件，分别是

httpd.conf
Apache 服务器的配置文件，用来加载 JK 模块以及指定 JK 配置文件信息

workers.properties
到 Tomcat 服务器的连接定义文件

uriworkermap.properties
URI 映射文件，用来指定哪些 URL 由 Tomcat 处理，你也可以直接在 httpd.conf 中配置这些 URI，但是独立这些配置的好处是 JK 模块会定期更新该文件的内容，使得我们修改配置的时候无需重新启动 Apache 服务器。

其中第二、三个配置文件名都可以自定义。下面是一个典型的 httpd.conf 对 JK 的配置

# (httpd.conf)
# 加载 mod_jk 模块
LoadModule jk_module modules/mod_jk.so

#
# Configure mod_jk
#

JkWorkersFile conf/workers.properties
JkMountFile conf/uriworkermap.properties
JkLogFile logs/mod_jk.log
JkLogLevel warn

接下来我们在 Apache 的 conf 目录下新建两个文件分别是 workers.properties、uriworkermap.properties。这两个文件的内容大概如下

#
# workers.properties
#


# list the workers by name

worker.list=DLOG4J, status

# localhost server 1
# ------------------------
worker.s1.port=8109
worker.s1.host=localhost
worker.s1.type=ajp13

# localhost server 2
# ------------------------
worker.s2.port=8209
worker.s2.host=localhost
worker.s2.type=ajp13
worker.s2.stopped=1

worker.DLOG4J.type=lb
worker.retries=3
worker.DLOG4J.balanced_workers=s1, s2
worker.DLOG4J.sticky_session=1

worker.status.type=status

以上的 workers.properties 配置就是我们前面那个屏幕抓图的页面所用的配置。首先我们配置了两个类型为 ajp13 的 worker 分别是 s1 和 s2，它们指向同一台服务器上运行在两个不同端口 8109 和 8209 的 Tomcat 上。接下来我们配置了一个类型为 lb（也就是负载均衡的意思）的 worker，它的名字是 DLOG4J，这是一个逻辑的 worker，它用来管理前面配置的两个物理连接 s1 和 s2。最后还配置了一个类型为 status 的 worker，这是用来监控 JK 本身的模块。有了这三个 worker 还不够，我们还需要告诉 JK，哪些 worker 是可用的，所以就有 worker.list = DLOG4J, status 这行配置。

接下来便是 URI 的映射配置了，我们需要指定哪些链接是由 Tomcat 处理的，哪些是由 Apache 直接处理的，看看下面这个文件你就能明白其中配置的意义

/*=DLOG4J
/jkstatus=status

!/*.gif=DLOG4J
!/*.jpg=DLOG4J
!/*.png=DLOG4J
!/*.css=DLOG4J
!/*.js=DLOG4J
!/*.htm=DLOG4J
!/*.html=DLOG4J

相信你已经明白了一大半了：所有的请求都由 DLOG4J 这个 worker 进行处理，但是有几个例外，/jkstatus 请求由 status 这个 worker 处理。另外这个配置中每一行数据前面的感叹号是什么意思呢？感叹号表示接下来的 URI 不要由 JK 进行处理，也就是 Apache 直接处理所有的图片、css 文件、js 文件以及静态 html 文本文件。

通过对 workers.properties 和 uriworkermap.properties 的配置，可以有各种各样的组合来满足我们前面提出对一个 web 网站的要求。您不妨动手试试！

回页首

http_proxy

这是利用 Apache 自带的 mod_proxy 模块使用代理技术来连接 Tomcat。在配置之前请确保是否使用的是 2.2.x 版本的 Apache 服务器。因为 2.2.x 版本对这个模块进行了重写，大大的增强了其功能和稳定性。

http_proxy 模式是基于 HTTP 协议的代理，因此它要求 Tomcat 必须提供 HTTP 服务，也就是说必须启用 Tomcat 的 HTTP Connector。一个最简单的配置如下

ProxyPass /images !
ProxyPass /css !
ProxyPass /js !
ProxyPass / http://localhost:8080/

在这个配置中，我们把所有 http://localhost 的请求代理到 http://localhost:8080/ ，这也就是 Tomcat 的访问地址，除了 images、css、js 几个目录除外。我们同样可以利用 mod_proxy 来做负载均衡，再看看下面这个配置

ProxyPass /images !
ProxyPass /css ! 
ProxyPass /js !

ProxyPass / balancer://example/
<Proxy balancer://example/>
BalancerMember http://server1:8080/
BalancerMember http://server2:8080/
BalancerMember http://server3:8080/
</Proxy>

配置比 JK 简单多了，而且它也可以通过一个页面来监控集群运行的状态，并做一些简单的维护设置。

回页首

ajp_proxy

ajp_proxy 连接方式其实跟 http_proxy 方式一样，都是由 mod_proxy 所提供的功能。配置也是一样，只需要把 http:// 换成 ajp:// ，同时连接的是 Tomcat 的 AJP Connector 所在的端口。上面例子的配置可以改为：

ProxyPass /images !
ProxyPass /css ! 
ProxyPass /js !

ProxyPass / balancer://example/
<Proxy balancer://example/>
BalancerMember ajp://server1:8080/
BalancerMember ajp://server2:8080/
BalancerMember ajp://server3:8080/
</Proxy>

采用 proxy 的连接方式，需要在 Apache 上加载所需的模块，mod_proxy 相关的模块有 mod_proxy.so、mod_proxy_connect.so、mod_proxy_http.so、mod_proxy_ftp.so、 mod_proxy_ajp.so， 其中 mod_proxy_ajp.so 只在 Apache 2.2.x 中才有。如果是采用 http_proxy 方式则需要加载 mod_proxy.so 和 mod_proxy_http.so；如果是 ajp_proxy 则需要加载 mod_proxy.so 和 mod_proxy_ajp.so这两个模块。

回页首

三者比较

相对于 JK 的连接方式，后两种在配置上是比较简单的，灵活性方面也一点都不逊色。但就稳定性而言就不像 JK 这样久经考验，毕竟 Apache 2.2.3 推出的时间并不长，采用这种连接方式的网站还不多，因此，如果是应用于关键的互联网网站，还是建议采用 JK 的连接方式。

参考资料

• 获得 Apache Http Server。
  
  
• 获得 Apache Tomcat。
  
  
• JK 文档。
  
  

关于作者

sed(C)

Syntax

sed [ -n ] [ -e script ] ... [ -f sfile ] ... [ file ... ]

Description

sed takes the following options:

-e script

Read the command script; usually quoted to protect it from the shell.

-f sfile

Take the script from the file sfile; these options accumulate. If there is just one -e option and no -f options, the flag -e may be omitted.

-n

Suppress the default output.

In normal operation, sed cyclically copies a line of input into a pattern space (unless there is something left after a D command), applies in sequence all commands whose addresses select that pattern space, and at the end of the script copies the pattern space to the standard output (except under -n) and deletes the pattern space.

A semicolon ``;'' can be used as a command delimiter.

Some of the commands use a hold space to save all or part of the pattern space for subsequent retrieval (see the ``Limitations'' section).

An address is either a decimal number that counts input lines cumulatively across files, a ``$'' that addresses the last line of input, or a context address, that is, a /regular expression/ as described in regexp(M), modified as follows:

• In a context address, the construction \?regular expression?, where ``?'' is any character, is identical to /regular expression/. Note that in the context address \xabc\xdefx, the second x stands for itself, so that the standard expression is abcxdef.
• The escape sequence \n matches a newline embedded in the pattern space.
• A dot (.) matches any character except the terminal newline of the pattern space.
• A command line with no addresses selects every pattern space.
• A command line with one address selects each pattern space that matches the address.
• A command line with two addresses separated by a comma selects the inclusive range from the first pattern space that matches the first address through the next pattern space that matches the second. (If the second address is a number less than or equal to the line number first selected, only one line is selected.) Thereafter, the process is repeated, looking again for the first address.

Functions

The text argument consists of one or more lines, all but the last of which end with backslashes to hide the newlines. Backslashes in text are treated like backslashes in the replacement string of an s command, and may be used to protect initial blanks and tabs against the stripping that is done on every script line.

The rfile or wfile argument must terminate the command line and must be preceded by one blank. Each wfile is created before processing begins. There can be at most 10 distinct wfile arguments.

(1) a\
text

Appends text, placing it on the output before reading the next input line. Note that there must be a line break between the command and the text.

(2) b label

Branches to the : command bearing the label. If label is empty, branches to the end of the script.

(2) c\
text

Changes text by deleting the pattern space and then appending text. With 0 or 1 address or at the end of a 2-address range, places text on the output and starts the next cycle. Note that there must be a line break between the command and the text.

(2) d

Deletes the pattern space and starts the next cycle.

(2) D

Deletes the initial segment of the pattern space through the first newline and starts the next cycle.

(2) g

Replaces the contents of the pattern space with the contents of the hold space.

(2) G

Appends the contents of the hold space to the pattern space.

(2) h

Replaces the contents of the hold space with the contents of the pattern space.

(2) H

Appends the contents of the pattern space to the hold space.

(1) i\
text

Insert. Places text on the standard output. Note that there must be a line break between the command and the text.

(2) l

Lists the pattern space on the standard output in an unambiguous way. Nonprinting characters are displayed as a three digit octal number preceded by a backslash ``\''. The following characters are printed as escape sequences:

 -------------------------------------------
 Character              Output
 -------------------------------------------
 backslash              \\
 alert (bell)           \a
 backspace              \b
 form feed              \f
 carriage return        \r
 horizontal tab         \t
 vertical tab           \v

Any output lines that are longer than the output device width (determined by the environment variable COLUMNS) are folded into multiple lines. New lines, inserted when folding a long line, are escaped by a preceding backslash character. The ends of each line in the pattern space are denoted by a dollar character ``$''.

(2) n

Copies the pattern space to the standard output. Replaces the pattern space with the next line of input.

(2) N

Appends the next line of input to the pattern space with an embedded newline. (The current line number changes.)

(2) p

Prints (copies) the pattern space on the standard output.

(2) P

Prints (copies) the initial segment of the pattern space through the first newline to the standard output.

(1) q

Quits sed by branching to the end of the script. No new cycle is started.

(2) r rfile

Reads the contents of rfile and places them on the output before reading the next input line.

(2) s /regular expression/replacement/flags

Substitutes the replacement string for instances of the regular expression in the pattern space. Any character may be used instead of ``/''. For a more detailed description, see regexp(M).

Flags is zero or more of:

n

Substitute for just the nth occurrence of the regular expression. n must be an integer greater than zero.

g

Globally substitutes for all non-overlapping instances of the regular expression rather than just the first one.

p

Prints the pattern space if a replacement was made.

w wfile

Writes the pattern space to wfile if a replacement was made.

(2) t label

Branches to the colon (:) command bearing label if any substitutions have been made since the most recent reading of an input line or execution of a t command. If label is empty, t branches to the end of the script.

(2) w wfile

Writes the pattern space to wfile.

(2) x

Exchanges the contents of the pattern and hold spaces.

(2) y /string1/string2/

Replaces all occurrences of characters in string1 with the corresponding characters in string2. The lengths of string1 and string2 must be equal.

(2) ! function

Applies the function (or group, if function is ``{'') only to lines not selected by the address(es).

(0) : label

This command does nothing; it bears a label for b and t commands to branch to. Labels can be at most 8 characters long.

(1) =

Places the current line number on the standard output as a line.

(2) {

Executes the following commands through a matching ``}'' only when the pattern space is selected.

(2) !{

Executes the following commands through a matching ``}'' only when the pattern space is not selected.

(0)

An empty command is ignored.

(0) #

Ignore the remainder of the line if # is followed by any other character than ``n'' (treat the line as a comment); if the character ``n'' follows #, suppress the default output (equivalent to the command line option -n).

Environment variables

COLUMNS

The width of the standard output device in characters; used by the l command for folding long lines. If this variable is not set or it has an invalid value, sed uses the default value 72.

Exit values

Examples

A common use of sed is to edit a file from within a shell script. In this example, every occurrence of the string ``sysman'' in the file infile is replaced by ``System Manager''. A temporary file TMP is used to hold the intermediate result of the edit:

   TMP=/usr/tmp/tmpfile_$$
   sed -e 's/sysman/System Manager/g' < infile > $TMP
   mv $TMP infile

   sed '
   /^$/ d
   /^[<Tab><Space>]*$/ d
   ´ padded_file 

If several editing commands must be carried out on a file, but the parameters for the edit are to be supplied by the user, then use echo to append command lines to a sed script. The following example removes all occurrences of the strings given as arguments to the script from the file infile. The name of the temporary file is held by the variable SCRIPT:

   SCRIPT=/usr/tmp/script_$$


   for name in $*
   do
   	echo "s/${name}//g" >> $SCRIPT
   done
   

   TMPFILE=/usr/tmp/tmpfile_$$
   

   sed -f $SCRIPT < infile > $TMPFILE
   

   mv $TMPFILE infile
   

   rm $SCRIPT

Limitations

See also

Chapter 14, ``Manipulating text with sed'' in the Operating System User's Guide

Standards conformance

ISO/IEC DIS 9945-2:1992, Information technology - Portable Operating System Interface (POSIX) - Part 2: Shell and Utilities (IEEE Std 1003.2-1992);
AT&T SVID Issue 2;
X/Open CAE Specification, Commands and Utilities, Issue 4, 1992.

SCO OpenServer Release 5.0.6 -- 1 August 2000

The C Library Reference Guide

Introduction

1.   Language
     1.1  Characters
          1.1.1     Trigraph Characters
          1.1.2     Escape Sequences
          1.1.3     Comments
     1.2  Identifiers
          1.2.1     Keywords
          1.2.2     Variables
          1.2.3     Enumerated Tags
          1.2.4     Arrays
          1.2.5     Structures and Unions
          1.2.6     Constants
          1.2.7     Strings
          1.2.8     sizeof Keyword
     1.3  Functions
          1.3.1     Definition
          1.3.2     Program Startup
     1.4  References
          1.4.1     Pointers and the Address Operator
          1.4.2     Typecasting
     1.5  Operators
          1.5.1     Postfix
          1.5.2     Unary and Prefix
          1.5.3     Normal
          1.5.4     Boolean
          1.5.5     Assignment
          1.5.6     Precedence
     1.6  Statements
          1.6.1     if
          1.6.2     switch
          1.6.3     while  
          1.6.4     do
          1.6.5     for
          1.6.6     goto
          1.6.7     continue
          1.6.8     break
          1.6.9     return
     1.7  Preprocessing Directives
          1.7.1     #if, #elif, #else, #endif
          1.7.2     #define, #undef, #ifdef, #ifndef
          1.7.3     #include
          1.7.4     #line
          1.7.5     #error
          1.7.6     #pragma
          1.7.7     Predefined Macros
2.   Library
     2.1  assert.h
          2.1.1     assert
     2.2  ctype.h
          2.2.1     is... Functions
          2.2.2     to... Functions
     2.3  errno.h 
          2.3.1     EDOM
          2.3.2     ERANGE
          2.3.3     errno   
     2.4  float.h
          2.4.1     Defined Values
     2.5  limits.h
          2.5.1     Defined Values
     2.6  locale.h
          2.6.1     Variables and Definitions
          2.6.2     setlocale
          2.6.3     localeconv
     2.7  math.h
          2.7.1     Error Conditions
          2.7.2     Trigonometric Functions
               2.7.2.1   acos
               2.7.2.2   asin
               2.7.2.3   atan
               2.7.2.4   atan2
               2.7.2.5   cos
               2.7.2.6   cosh
               2.7.2.7   sin
               2.7.2.8   sinh
               2.7.2.9   tan
               2.7.2.10  tanh
          2.7.3     Exponential, Logarithmic, and Power Functions
               2.7.3.1   exp
               2.7.3.2   frexp
               2.7.3.3   ldexp
               2.7.3.4   log
               2.7.3.5   log10
               2.7.3.6   modf
               2.7.3.7   pow
               2.7.3.8   sqrt
          2.7.4     Other Math Functions
               2.7.4.1   ceil
               2.7.4.2   fabs
               2.7.4.3   floor
               2.7.4.4   fmod
     2.8  setjmp.h
          2.8.1     Variables and Definitions
          2.8.2     setjmp
          2.8.3     longjmp
     2.9  signal.h
          2.9.1     Variables and Definitions
          2.9.2     signal
          2.9.3     raise
     2.10 stdarg.h
          2.10.1    Variables and Definitions
          2.10.2    va_start
          2.10.3    va_arg
          2.10.4    va_end
     2.11 stddef.h
          2.11.1    Variables and Definitions
     2.12 stdio.h
          2.12.1    Variables and Definitions
          2.12.2    Streams and Files
          2.12.3    File Functions
               2.12.3.1  clearerr
               2.12.3.2  fclose
               2.12.3.3  feof
               2.12.3.4  ferror
               2.12.3.5  fflush
               2.12.3.6  fgetpos
               2.12.3.7  fopen
               2.12.3.8  fread
               2.12.3.9  freopen
               2.12.3.10 fseek
               2.12.3.11 fsetpos
               2.12.3.12 ftell
               2.12.3.13 fwrite
               2.12.3.14 remove
               2.12.3.15 rename
               2.12.3.16 rewind
               2.12.3.17 setbuf
               2.12.3.18 setvbuf
               2.12.3.19 tmpfile
               2.12.3.20 tmpnam
          2.12.4    Formatted I/O Functions
               2.12.4.1  ...printf Functions
               2.12.4.2  ...scanf Functions
          2.12.5    Character I/O Functions
               2.12.5.1  fgetc
               2.12.5.2  fgets
               2.12.5.3  fputc
               2.12.5.4  fputs
               2.12.5.5  getc
               2.12.5.6  getchar
               2.12.5.7  gets
               2.12.5.8  putc
               2.12.5.9  putchar
               2.12.5.10 puts
               2.12.5.11 ungetc
          2.12.7    Error Functions
               2.12.7.1  perror
     2.13 stdlib.h
          2.13.1    Variables and Definitions
          2.13.2    String Functions
               2.13.2.1  atof
               2.13.2.2  atoi
               2.13.2.3  atol
               2.13.2.4  strtod
               2.13.2.5  strtol
               2.13.2.6  strtoul
          2.13.3    Memory Functions
               2.13.3.1  calloc
               2.13.3.2  free
               2.13.3.3  malloc
               2.13.3.4  realloc
          2.13.4    Environment Functions
               2.13.4.1  abort
               2.13.4.2  atexit
               2.13.4.3  exit
               2.13.4.4  getenv
               2.13.4.5  system
          2.13.5    Searching and Sorting Functions
               2.13.5.1  bsearch
               2.13.5.2  qsort
          2.13.6    Math Functions  
               2.13.6.1  abs
               2.13.6.2  div
               2.13.6.3  labs
               2.13.6.4  ldiv
               2.13.6.5  rand
               2.13.6.6  srand
          2.13.7    Multibyte Functions
               2.13.7.1  mblen
               2.13.7.2  mbstowcs
               2.13.7.3  mbtowc
               2.13.7.4  wcstombs
               2.13.7.5  wctomb
     2.14 string.h
          2.14.1    Variables and Definitions
          2.14.2    memchr
          2.14.3    memcmp
          2.14.4    memcpy
          2.14.5    memmove
          2.14.6    memset
          2.14.7    strcat
          2.14.8    strncat
          2.14.9    strchr
          2.14.10   strcmp
          2.14.11   strncmp
          2.14.12   strcoll
          2.14.13   strcpy
          2.14.14   strncpy
          2.14.15   strcspn
          2.14.16   strerror
          2.14.17   strlen
          2.14.18   strpbrk
          2.14.19   strrchr
          2.14.20   strspn
          2.14.21   strstr
          2.14.22   strtok
          2.14.23   strxfrm
     2.15 time.h 
          2.15.1    Variables and Definitions
          2.15.2    asctime
          2.15.3    clock
          2.15.4    ctime
          2.15.5    difftime
          2.15.6    gmtime
          2.15.7    localtime
          2.15.8    mktime
          2.15.9    strftime
          2.15.10   time
Appendix A
	ASCII Chart
Index
	Index