为何Ruby实现的BST插入600万条数据速度极慢？求优化方案

我用Ruby实现了如下非递归的简单二叉搜索树（BST）：

class Node
  attr_accessor :data, :left, :right
  
  def initialize data
    @data = data
  end
end

def insert root, data
  current = root
  
  loop do
    node = current.data < data ? current.right : current.left
    break if node.nil?
    current = node
  end
  
  if current.data < data
    current.right = Node.new(data)
  else
    current.left = Node.new(data)
  end
end

注：由于BST规模较大时会出现“栈溢出”异常，因此未使用递归实现。

随后我尝试插入约600万条记录：

root = Node.new('root')
insert root, "something"
insert root, "another"
# ...

在MacOS上完成插入耗时约30分钟，这速度实在太慢！

为何该BST插入速度如此缓慢（使用SQLite对相同数据建立索引仅需30秒）？能否针对上述代码给出优化建议？

• BST的不平衡问题：普通BST在插入有序（或近似有序）数据时会退化成链表，插入时间复杂度从O(log n)骤降为O(n)，600万条数据的总操作次数会达到量级极高的水平，直接导致性能崩溃。而SQLite的索引基于B+树（平衡树结构），会自动维持树的平衡，保证插入操作的时间复杂度稳定在O(log n)。
• Ruby对象创建的开销：每次插入都要新建Node对象，600万次的对象初始化会带来大量内存分配和GC压力，这在Ruby中是较为耗时的操作。
• 字符串比较的额外成本：插入的是字符串数据，Ruby中字符串比较本身比数值比较慢，若字符串长度较长，每次比较的开销会进一步增大。

1. 改用自平衡二叉搜索树 #

替换普通BST为AVL树或红黑树，这类结构会自动维持树的平衡，避免退化问题，保证插入操作的时间复杂度稳定在O(log n)。Ruby标准库没有内置实现，但可以自行编写，或使用第三方库（如rbtree）。

2. 降低对象创建开销 #

• 采用对象池机制：预先分配一批Node对象，复用空闲节点，减少频繁的内存分配与销毁。
• 用Struct替代普通类：Struct在Ruby中的创建和访问速度优于普通类，可将Node定义改为：

Node = Struct.new(:data, :left, :right)

3. 优化插入逻辑，减少重复计算 #

当前代码在循环内和循环结束后各做了一次字符串比较，可缓存比较结果，同时改用<=>运算符一次性得到比较结果，提升效率：

def insert(root, data)
  current = root
  loop do
    cmp = current.data <=> data
    node = cmp < 0 ? current.right : current.left
    break if node.nil?
    current = node
  end
  cmp = current.data <=> data
  if cmp < 0
    current.right = Node.new(data)
  else
    current.left = Node.new(data)
  end
end

4. 批量插入优化 #

若数据可预先排序，使用有序数组构建平衡二叉树的方法，时间复杂度为O(n)，远快于逐个插入。

5. 利用Ruby内置优化结构 #

如果不需要自行实现BST，直接使用Ruby内置的高效结构：

• Hash：底层为哈希表，平均插入时间O(1)，适合快速查找场景。
• SortedSet：来自set标准库，基于红黑树实现的有序集合，经过高度优化，性能远超自行实现的BST：

require 'set'
sorted_set = SortedSet.new
data_list.each { |data| sorted_set.add(data) }

内容的提问来源于stack exchange，提问作者collimarco