Index: head/sys/fs/autofs/autofs.h
===================================================================
--- head/sys/fs/autofs/autofs.h
+++ head/sys/fs/autofs/autofs.h
@@ -65,11 +65,12 @@
 #define AUTOFS_ASSERT_UNLOCKED(X)	sx_assert(&X->am_lock, SA_UNLOCKED)
 
 struct autofs_node {
-	TAILQ_ENTRY(autofs_node)	an_next;
+	RB_ENTRY(autofs_node)		an_link;
 	char				*an_name;
 	int				an_fileno;
 	struct autofs_node		*an_parent;
-	TAILQ_HEAD(, autofs_node)	an_children;
+	RB_HEAD(autofs_node_tree,
+	    autofs_node)		an_children;
 	struct autofs_mount		*an_mount;
 	struct vnode			*an_vnode;
 	struct sx			an_vnode_lock;
@@ -136,4 +137,6 @@
 int	autofs_node_vn(struct autofs_node *anp, struct mount *mp,
 	    int flags, struct vnode **vpp);
 
+RB_PROTOTYPE(autofs_node_tree, autofs_node, an_link, autofs_node_cmp);
+
 #endif /* !AUTOFS_H */
Index: head/sys/fs/autofs/autofs.c
===================================================================
--- head/sys/fs/autofs/autofs.c
+++ head/sys/fs/autofs/autofs.c
@@ -77,6 +77,7 @@
 #include <sys/sysctl.h>
 #include <sys/syscallsubr.h>
 #include <sys/taskqueue.h>
+#include <sys/tree.h>
 #include <sys/vnode.h>
 #include <machine/atomic.h>
 #include <vm/uma.h>
@@ -149,6 +150,15 @@
 SYSCTL_INT(_vfs_autofs, OID_AUTO, interruptible, CTLFLAG_RWTUN,
     &autofs_interruptible, 1, "Allow requests to be interrupted by signal");
 
+static int
+autofs_node_cmp(const struct autofs_node *a, const struct autofs_node *b)
+{
+
+	return (strcmp(a->an_name, b->an_name));
+}
+
+RB_GENERATE(autofs_node_tree, autofs_node, an_link, autofs_node_cmp);
+
 int
 autofs_init(struct vfsconf *vfsp)
 {
Index: head/sys/fs/autofs/autofs_vfsops.c
===================================================================
--- head/sys/fs/autofs/autofs_vfsops.c
+++ head/sys/fs/autofs/autofs_vfsops.c
@@ -42,6 +42,7 @@
 #include <sys/stat.h>
 #include <sys/sx.h>
 #include <sys/taskqueue.h>
+#include <sys/tree.h>
 #include <sys/vnode.h>
 
 #include <fs/autofs/autofs.h>
@@ -158,10 +159,10 @@
 	/*
 	 * Not terribly efficient, but at least not recursive.
 	 */
-	while (!TAILQ_EMPTY(&amp->am_root->an_children)) {
-		anp = TAILQ_FIRST(&amp->am_root->an_children);
-		while (!TAILQ_EMPTY(&anp->an_children))
-			anp = TAILQ_FIRST(&anp->an_children);
+	while (!RB_EMPTY(&amp->am_root->an_children)) {
+		anp = RB_MIN(autofs_node_tree, &amp->am_root->an_children);
+		while (!RB_EMPTY(&anp->an_children))
+			anp = RB_MIN(autofs_node_tree, &anp->an_children);
 		autofs_node_delete(anp);
 	}
 	autofs_node_delete(amp->am_root);
Index: head/sys/fs/autofs/autofs_vnops.c
===================================================================
--- head/sys/fs/autofs/autofs_vnops.c
+++ head/sys/fs/autofs/autofs_vnops.c
@@ -44,6 +44,7 @@
 #include <sys/stat.h>
 #include <sys/systm.h>
 #include <sys/taskqueue.h>
+#include <sys/tree.h>
 #include <sys/vnode.h>
 #include <machine/atomic.h>
 #include <vm/uma.h>
@@ -450,7 +451,7 @@
 	 * Write out the directory entries for subdirectories.
 	 */
 	AUTOFS_SLOCK(amp);
-	TAILQ_FOREACH(child, &anp->an_children, an_next) {
+	RB_FOREACH(child, autofs_node_tree, &anp->an_children) {
 		/*
 		 * Check the offset to skip entries returned by previous
 		 * calls to getdents().
@@ -575,8 +576,8 @@
 	anp->an_parent = parent;
 	anp->an_mount = amp;
 	if (parent != NULL)
-		TAILQ_INSERT_TAIL(&parent->an_children, anp, an_next);
-	TAILQ_INIT(&anp->an_children);
+		RB_INSERT(autofs_node_tree, &parent->an_children, anp);
+	RB_INIT(&anp->an_children);
 
 	*anpp = anp;
 	return (0);
@@ -586,27 +587,28 @@
 autofs_node_find(struct autofs_node *parent, const char *name,
     int namelen, struct autofs_node **anpp)
 {
-	struct autofs_node *anp;
+	struct autofs_node *anp, find;
+	int error;
 
 	AUTOFS_ASSERT_LOCKED(parent->an_mount);
 
-	TAILQ_FOREACH(anp, &parent->an_children, an_next) {
-		if (namelen >= 0) {
-			if (strlen(anp->an_name) != namelen)
-				continue;
-			if (strncmp(anp->an_name, name, namelen) != 0)
-				continue;
-		} else {
-			if (strcmp(anp->an_name, name) != 0)
-				continue;
-		}
+	if (namelen >= 0)
+		find.an_name = strndup(name, namelen, M_AUTOFS);
+	else
+		find.an_name = strdup(name, M_AUTOFS);
 
+	anp = RB_FIND(autofs_node_tree, &parent->an_children, &find);
+	if (anp != NULL) {
+		error = 0;
 		if (anpp != NULL)
 			*anpp = anp;
-		return (0);
+	} else {
+		error = ENOENT;
 	}
 
-	return (ENOENT);
+	free(find.an_name, M_AUTOFS);
+
+	return (error);
 }
 
 void
@@ -615,13 +617,13 @@
 	struct autofs_node *parent;
 
 	AUTOFS_ASSERT_XLOCKED(anp->an_mount);
-	KASSERT(TAILQ_EMPTY(&anp->an_children), ("have children"));
+	KASSERT(RB_EMPTY(&anp->an_children), ("have children"));
 
 	callout_drain(&anp->an_callout);
 
 	parent = anp->an_parent;
 	if (parent != NULL)
-		TAILQ_REMOVE(&parent->an_children, anp, an_next);
+		RB_REMOVE(autofs_node_tree, &parent->an_children, anp);
 	sx_destroy(&anp->an_vnode_lock);
 	free(anp->an_name, M_AUTOFS);
 	uma_zfree(autofs_node_zone, anp);